53. Maximum Subarray

Leetcode Divide and Conquer Dynamic Programming Classic

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.

分析

连续子数组的最大和。解决的算法叫做Kadane's algorithm. 下面的话摘自Jon Bentley在ACM Communication的文章(被整理成一本书叫编程珠玑，该问题在编程珠玑第8章)。

algorithm that operates on arrays: it starts at the left end (element nums[1]) and scans through to the right end (element nums[$n$]), keeping track of the maximum sum subvector seen so far. The maximum is initially nums[0]. Suppose we've solved the problem for nums[$1 .. i - 1$]; how can we extend that to nums[1 .. $i$]? The maximum sum in the first $i$ elements is either the maximum sum in the first $i - 1$ elements (which we'll call maxSoFar), or it is that of a subvector that ends in position $i$ (which we'll call maxEndingHere).

public int maxSubArray(int[] nums) {
    int maxSoFar = nums[0], maxEndingHere = nums[0];
    for (int i=1; i < nums.length; ++i){
        maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
     }
    return maxSoFar;
}

其中

maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);

也可以替换成

// only when the maxEndingHere is negative, 
// we start to calculate the sum again.
if (maxEndingHere < 0) maxEndingHere = nums[i];
else maxEndingHere += nums[i];

它们的含义和功能都是一样的。