Max Sum Contiguous Subarray

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

Given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

For this problem, return the maximum sum.

思路:

最简单的DP，遍历input，记录当前能拿到的Max Sum
dp[i] = max(dp[i - 1] + A[i], A[i])
返回max(dp[i])

Solution:

Time: O(n)
Space: O(n) -> 可以优化到 O(1)

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int maxSubArray(final List<Integer> A) {
        if (A.size() == 1) return A.get(0);
        int[] maxSum = new int[A.size()];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < A.size(); i ++) {
            int num = A.get(i);
            if (i == 0) {
                maxSum[i] = num;
            } else {
                maxSum[i] = Math.max(maxSum[i - 1] + num, num);
            }
            max = Math.max(max, maxSum[i]);
        }
        return max;
    }
}