求一個給定序列的最大連續(xù)子序列和夯秃，如[-2,1,-3,4,-1,2,1,-5,4]的最大連續(xù)子序列為[4, -1, 2, 1]
這是一個典型的動態(tài)規(guī)劃問題，中文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;
}
這里假設(shè)有一個長度與原序列相同的整形數(shù)組dp映挂，dp[i]表示原序列以i位置作為結(jié)尾時的子序列的最大和，那么當(dāng)dp[i - 1] > 0時dp[i]所表示的最大和可以轉(zhuǎn)化為dp[i - 1] + values[i]坊秸，而如果dp[i - 1] < 0，則說明前面的和是負(fù)數(shù)澎怒，應(yīng)該從下一位位置開始作為起點(diǎn)褒搔，即dp[i] = values[i]。這就是我們需要的轉(zhuǎn)移方程喷面。
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;
}
