Maximum Subarray

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

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

http://www.lintcode.com/en/problem/maximum-subarray/

Discussion

用个global表示max sum of the subarrays, update global with the previous local maximum plus the current number if needed.
The local maximum will be 0 if the sum of local and nums[i] is less than 0, which means we start from 0 in the next element.

Solution

class Solution {
public:    
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    int maxSubArray(vector<int> nums) {
        if(nums.empty()) return 0;
        int local = 0; 
        int global = INT_MIN;
        for(auto const &i : nums) {
            global = max(global, local+i);
            local  = max(0, local+i);
        }
        return global;
    }
};

Solution DP

maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element.
status update:
maxSubArray(A, i) = （maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0） + A[i];

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;
}

第一个Solution本质上也是DP，saving space version