Maximum Subarray

题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array[-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray[4,-1,2,1]has the largest sum =6.

分析

1. the curMax and preMax are both initially A[0]
2. it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far
3. preMax is either A[i] plus the previous preMax, or just A[i], whichever is larger
4. Suppose we’ve solved the problem for A[1 … i - 1]; how can we extend that to A[1 … i]? The maximum sum in the first I elements is either the maximum sum in the first i - 1 elements (which we’ll call curMax), or it is that of a subvector that ends in position i (which we’ll call preMax)

图解

解题

class Solution {
    public int maxSubArray(int[] A) {
        int curMax = A[0], preMax = A[0];
        for (int i = 1; i < A.length; i++){
            preMax = Math.max(preMax+A[i], A[i]);
            curMax = Math.max(curMax, preMax);
        }
        return curMax;
    }
}