第一種算法O(N^3)
public static int maxSubSum1(int a[]){ int maxSum=0; for(int i=0;i<a.length;i++){ for(int j=i;j<a.length;j++){ int thisSum=0; for( int k=i;k<j;k++){ thisSum+= a[k]; } if(thisSum>maxSum) maxSum=thisSum; } } return maxSum; }第二種算法O(N^2)
public static int maxSubSum2(int a[]){ int maxSum=0; for(int i=0;i<a.length;i++){ int thisSum=0; for(int j=i;j<a.length;j++){ thisSum +=a[j]; if(thisSum>maxSum) maxSum = thisSum; } } return maxSum; }第三種算法O(N logN),分治法 最大子序列的和可能在三處出現，或者出現在輸入數據的左半部，或者出現在輸入數據的右半部份，或者出現在輸入數據的中間部分。前兩種情況可以遞歸求解，第三種情況的最大和可以通過求出前半部分（包含前半部分最后一個元素）的最大和以及后半部分（包含后半部分第一個元素）的最大和而得到。此時將這兩個相加。
public static int maxSumRec(int a[] ,int left,int right){ if(left== right){ if(a[left]>0) return a[left]; else return 0; } int center = (left+right)/2; int maxLeftSum = maxSumRec(a,left,center); int maxRightSum = maxSumRec(a,center+1,right); int maxLeftBorderSum = 0,leftBorderSum = 0; for(int i=center;i>=left;i--){ leftBorderSum+= a[i]; if(leftBorderSum > maxLeftBorderSum){ maxLeftBorderSum = leftBorderSum; } } int maxRightBorderSum = 0,rightBorderSum = 0; for(int i=center+1;i<=right;i++){ rightBorderSum+= a[i]; if(rightBorderSum > maxRightBorderSum){ maxRightBorderSum = rightBorderSum; } } return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum); } PRivate static int max3(int a, int b, int c) { int ab = Math.max(a, b); return Math.max(c, ab); } public static int maxSubSum3(int a[]){ return maxSumRec(a, 0, a.length-1); }第四種算法O(N) 這種算法是比較難看出正確性的。可以知道，當a[i]是負的時，那么它不可能作為最有序列的起點，因為任何包含a[i]的作為起點的序列都可以通過用a[i+1]作為起點而得到改進。類似地，任何負的子序列不可能是最優子序列的前綴。如果在循環中檢測到從a[i]到a[j]的子序列是負的，那么可以推進i。關鍵的結論是，我們不僅可以把i推進到i+1, 而且實際上還可以把它一直推進到j+1。為了看清楚這一點，令p為i+1到j之間的任一下標。開始于下標p的任意子序列都不大于在下標i開始并包含從a[i]到a[p-1]的子序列的對應的子序列，因為后面的這個子序列不是負的（j是使得從下標i開始其值成為負值的序列的第一個下標）。因此，把i推進到j+1是沒有風險的。
public static int maxSubSum4(int a[]){ int maxSum=0,thisSum=0; for(int i=0;i<a.length;i++){ thisSum+=a[i]; if(thisSum>maxSum) maxSum = thisSum; else if(thisSum<0) thisSum = 0; } return maxSum; }新聞熱點
疑難解答
