LeetCode-Maximum Subarray

Love The Way You Lie 2022-08-04 11:50 36阅读 0赞

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array `[−2,1,−3,4,−1,2,1,−5,4]`,  
the contiguous subarray `[4,−1,2,1]` has the largest sum = `6`.

非常一道经典的一维动态规划题。 [Maximum subarray problem][] WIKI上也有关于这道题的解答，此算法为K adane's algorithm。

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

解法非常直观，maxEndingHere是指以sum(0, i)，即起点为o，终点为i这一段的最大值。而此时对于第i个元素有两个选择，要么加入之前的和之中，即maxEndingHere+nums\[i\]，否则不用之前的和。取最大值即可。公式表示为：

sum\[i\] = max(nums\[i\], sum\[i-1\] + nums\[i+1\])  
result = max(result, sum\[i\])

显然nums\[i\]与nums\[i\]+sum\[i-1\]孰大孰小，完全取决于sum\[i-1\]的正负，所以代码也可以这样写：

public int maxSubArray(int[] A) {
            if (A == null || A.length == 0) {
        		return 0;
        	}
        	int max = A[0];
        	int curSum = A[0];
        	for (int i = 1; i < A.length; i++) {
        		if (curSum < 0) {
        			curSum = A[i];
        		} else {
        			curSum += A[i];
        		}
        		if (max < curSum) {
        			max = curSum;
        		}
        	}
        	return max;
        }

这个算法还是比较经典的，好多算法也用到了这个特性，比如，maxEndingHere或者maxBeginingHere。

[Maximum subarray problem]: https://en.wikipedia.org/wiki/Maximum_subarray_problem