53. Maximum Subarray

求一个给定序列的最大连续子序列和，如[-2,1,-3,4,-1,2,1,-5,4]的最大连续子序列为[4, -1, 2, 1]
这是一个典型的动态规划问题，中文wiki页。

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

这里假设有一个长度与原序列相同的整形数组dp，dp[i]表示原序列以i位置作为结尾时的子序列的最大和，那么当dp[i - 1] > 0时dp[i]所表示的最大和可以转化为dp[i - 1] + values[i]，而如果dp[i - 1] < 0，则说明前面的和是负数，应该从下一位位置开始作为起点，即dp[i] = values[i]。这就是我们需要的转移方程。

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