Maximum Subarray

Given an integer arraynums, 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.

这题最直接的可能就是贪心法。算当前的streak，如果大于0一直加，并一路上记录最大值。一旦streak掉到0以下，就从头来过。因为掉到0一下，前面的数的和就是负担了。

    def maxSubArray(self, nums):

        if len(nums) == 0:
            return 0
        currentSum = 0
        best = nums[0]
        for n in nums:
            currentSum += n
            best = max(currentSum, best)
            if currentSum < 0:
                currentSum = 0

        return best

借用prefix 法

    def maxSubArray(self, nums):
        if len(nums) == 0:
            return 0
        prefix = 0
        prefixmin = 0
        best = nums[0]
        for n in nums:
            prefix += n
            best = max(best, prefix - prefixmin)
            prefixmin = min(prefixmin, prefix)

        return best

九章上看到一个“有趣”的方法

    public int maxSubArray(int[] nums) {
        // write your code
        if(nums.length == 0){
            return 0; 
        }
        int n = nums.length;
        int[] global = new int[2];
        int[] local = new int[2];
        global[0] = nums[0];
        local[0] = nums[0];
        for(int i = 1; i < n; i ++) {  
            local[i % 2] = Math.max(nums[i], local[(i - 1) % 2] + nums[i]);  
            global[i % 2] = Math.max(local[i % 2], global[(i - 1) % 2]);  
        }  
        return global[(n-1) % 2];  
    }

LeetCode 的 discuss 上看到的 DP 的方法

Explanation

Although there’re some other simplified solutions, but DP solution can make the original thought for this problem clearer. In this solution, dp[i] means the largest sum among the subarrays whose last element is A[i].

Solution1. DP Solution - O(n) time, O(n) space

public int maxSubArray(int[] A) {
    int dp[] = new int[A.length]; int max = A[0]; dp[0] = A[0]; 
    for (int i = 1; i < A.length; i++) {            
        dp[i] = Math.max(dp[i-1] + A[i] ,A[i]);
        max = Math.max(max, dp[i]);
    }
    return max;
}

LeetCode 的 discuss 上看到的 Divide and conquer 的方法。好复杂

For each subarray, calculate four attributes:

mx (largest sum of this subarray), 
lmx(largest sum starting from the left most element), 
rmx(largest sum ending with the right most element), 
sum(the sum of the total subarray).

The recurrence is: T(n) = 2T(n / 2) + O(1). So the running time of this algorithm is O(n).

class Solution {
public:
    void maxSubArray(vector<int>& nums, int l, int r, int& mx, int& lmx, int& rmx, int& sum) {
        if (l == r) {
            mx = lmx = rmx = sum = nums[l];
        }
        else {
            int m = (l + r) / 2;
            int mx1, lmx1, rmx1, sum1;
            int mx2, lmx2, rmx2, sum2;
            maxSubArray(nums, l, m, mx1, lmx1, rmx1, sum1);
            maxSubArray(nums, m + 1, r, mx2, lmx2, rmx2, sum2);
            mx = max(max(mx1, mx2), rmx1 + lmx2);
            lmx = max(lmx1, sum1 + lmx2);
            rmx = max(rmx2, sum2 + rmx1);
            sum = sum1 + sum2;
        }
    }
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int mx, lmx, rmx, sum;
        maxSubArray(nums, 0, nums.size() - 1, mx, lmx, rmx, sum);
        return mx;
    }
};

还有一个叫 Kadane's Algorithm https://www.youtube.com/watch?v=86CQq3pKSUw

其实思想和贪心法一样的，只不过做成了DP，好理解一点。dp[i] 的定义是，sum of the maximum subarray ending at index i.