53. 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:

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.

思路

只用记录两个变量,一个局部最优tempSum,一个全局最优maxSum。当局部最优小于零的时候就不考虑之前的数字,直接归零,然后依次得出全局最优。

代码

只用记录两个变量,一个是区间的临时总和tempSum,一个是和的最大值maxSum,然后遍历一次数组。假设遍历到第n个数,此时tempSum = tempSum + n。但是如果n之前的tempSum的值已经小于0了,我们就不用考虑他,因为下一个值不管是正数还是负数,加上tempSum值会变得更小。

1
2
3
4
5
6
7
8
9
//C++
int maxSubArray(vector<int>& nums) {
int maxSum = INT_MIN, tempSum = 0;
for(int n:nums) {
tempSum = n + (tempSum>0?tempSum:0);
maxSum = maxSum>tempSum?maxSum:tempSum;
}
return maxSum;
}

然后还在网上看到了动态规划法:

状态转移方程为:

1
maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i]; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//Java
public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];

for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}

return max;
}

https://leetcode.com/problems/maximum-subarray/discuss/20193/DP-solution-and-some-thoughts