53. Maximum Subarray

最大值就是当前prefixsum减去左边最小的prefix sum

class Solution {
    public int maxSubArray(int[] nums) {
        int[] psum = new int[nums.length];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            psum[i] = sum;
        }
        // 这里不能用MAX_VALUE和MIN_VALUE，因为可能会溢出
        int maxSum = -10001;
        int minPsum = 10001;
        for (int i = 0; i < nums.length; i++) {
            maxSum = Math.max(psum[i], Math.max(maxSum, psum[i]-minPsum));
            // minPsum要在maxSum更新之后更新，这样能排除空subarray有最大值的情况
            minPsum = Math.min(minPsum, psum[i]);
        }
        return maxSum;
    }
}

也可以用dp做， dp[i]就是i处结束的array的最大值，如果dp[i]+nums[i]还没有nums[i]大就另起炉灶

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