求一个给定序列的最大连续子序列和，如[-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;
}
