LeetCode53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


4/3/2019 二周目

今天是第二次做这道题了。只记得用DP,而且求sum的时候还比较错了。重新做一遍。

53

DP

DP就是要把大问题分解小问题,找到每个小问题的最优解,再从这些解里面找到最优解。

my codE in cpp

1
2
3
4
5
6
7
8
9
10
int maxSubArray(vector<int>& nums) {
if(nums.empty()) return 0;
int sum=0,_max=nums[0];
for(auto num:nums)
{
sum=max(sum+num,num);
_max=max(sum,_max);
}
return _max;
}
  • 开始误将num和_max比较,导致漏掉后面的最大子序列。应该将num和sum比较,找到subpro最大的子序列。
  • 因为最大子序列可能是分散的,求得每个最大子序列的和记为sum,在从这些sum中找到最大的和。
  • O(n) time

Divide and Conquer

  1. 二分法,分别求左右两边的最大序列和,不包含中点。
  2. 从中间开始,一直到两边端点,累计总和,记下分别到两边端点的最大和,包含中点。
  3. 比较二分的最大值 与 包含中点的最大值,哪个更大。

my code in cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return maxHelper(nums, 0, nums.size() - 1);
}
private:
int maxHelper(vector<int> &nums, int l, int r)
{
if (l > r) return INT_MIN;

int mid = l + (r - l) / 2;
int l_max = maxHelper(nums, l, mid - 1);
int r_max = maxHelper(nums, mid + 1, r);

int sum = nums[mid],m_max=nums[mid];

//link left
for (int i = mid - 1; i >= l; --i)
{
sum += nums[i];
m_max = max(m_max, sum);
}

sum = m_max;
//link right
for (int i = mid + 1; i <= r; i++)
{
sum += nums[i];
m_max = max(m_max, sum);
}

return max(max(l_max,r_max ),m_max);
}
};

3/15/2019 一周目

Optimization problem -DP

如果sum<=0,说明前面的可以不要了,sum=num。跟sum=max(sum+num,num)是一个意思,都是找子任务的最大值。用迭代器做了版本。

Newcoder in cpp

1
2
3
4
5
6
7
8
9
10
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.empty()) return 0;
int sum=0,_max=array[0];
for(auto it = array.begin();it!=array.end();it++)
{
sum>0? sum+=*it:sum=*it;
_max=max(_max,sum);
}
return _max;
}

my code in cpp 2

1
2
3
4
5
6
7
8
9
10
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.empty()) return 0;
int sum=0,_max=array[0];
for(auto it = array.begin();it!=array.end();it++)
{
sum=max(*it,sum+*it);
_max=max(_max,sum);
}
return _max;
}

Divide and Conquer

  • The Divide-and-Conquer algorithm breaks nums into two halves and find the maximum subarray sum in them recursively.
  • the maximum subarray spans the two halves.
  • a linear algorithm: starting from the middle element and move to both ends (left and right ends), record the maximum sum we have seen. In this case, the maximum sum is finally equal to the middle element plus the maximum sum of moving leftwards and the maximum sum of moving rightwards.
  • Since we are done with LHS and RHS, we only need to check the case where we pass the middle element.(i.e. the middle element must be included).In that case, since our question asks a continuous subset, it must expand that way.

2*O(n/2)+O(1)=O(n)

  • divide:用递归来分别求左右子集的max
  • merge:用dp来从左右分别线性探索,加上mid
  • 最后找到divide和merge中最大的就是要求的值。

LC in cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return maxSubArray(nums, 0, nums.size() - 1);
}
private:
int maxSubArray(vector<int>& nums, int l, int r) {
if (l > r) {
return INT_MIN;
}

//divide:
int m = l + (r - l) / 2;
int lmax = maxSubArray(nums, l, m - 1);//left
int rmax = maxSubArray(nums, m + 1, r);//right
int partmax = max(lmax, rmax);//not including mid

//Merge:
int ml= 0,mr = 0;
//left O(n/2)
for (int i = m - 1, sum = 0; i >= l; i--) {
sum += nums[i];
ml = max(sum, ml);
}
//right O(n/2)
for (int i = m + 1, sum = 0; i <= r; i++) {
sum += nums[i];
mr = max(sum, mr);
}
//Merge-including mid,for continuous subset:O(1)
int contmax=ml + mr + nums[m];

return max(partmax,contmax);
//2*O(n/2)+O(1)=O(n)
}
};

Thanks for Support.