第一种算法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; }新闻热点
疑难解答
