[LintCode] 41 Maximum Subarray 解题报告

Description
Given an array of integers, find a contiguous subarray which has the largest sum.


Notice
The subarray should contain at least one number.



Example
Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.



Challenge
Can you do it in time complexity O(n)?



思路
解法一：
看到subarray，会想到和prefixSum有关系。
我可以这样想：以当前index为终点的最大的subarray，等于以当前index为终点的prefixSum，减去到index之前的最小的prefixSum。
那么我们对于所有index，求出以index为终点的最大subarray，求个最大值就可以了。
这里要注意，我们在遍历数组的时候要维护最小的prefixSum。



Code

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        
        int prefixSum = 0;
        int minPrefixSum = 0;
        int maxPrefixSum = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            maxPrefixSum = Math.max(maxPrefixSum, prefixSum - minPrefixSum);
            minPrefixSum = Math.min(minPrefixSum, prefixSum);
        }
        
        return maxPrefixSum;
    }
}

解法二：

Kadane's Algorithm

DP的思想。

以index为终点的max subarray，是

1：以终点为index - 1的max subarray加上nums[index]

2：num[index]

这两者较大的那一个。

我们遍历数组，把所有的index都过一遍，并求出每一个index为终点的max subarray。取最大。

Code

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] localmax = new int[len];
        int[] globalmax = new int[len];
        localmax[0] = globalmax[0] = nums[0];
        for (int i = 1; i < len; i++) {
            localmax[i] = Math.max(localmax[i - 1] + nums[i], nums[i]);
            globalmax[i] = Math.max(globalmax[i - 1], localmax[i]);
        }
        return globalmax[len - 1];
    }
}