最大子序列和问题
给定（可能有负的）整数序列A1,A2,...An,求子序列的和的最大值（如果所有整数为负数，则最大子序列和为0）。
例如：对于输入 -2，11，-2,13，-5，-2，答案为20（从a2到a4）。
这个问题有4种解法，而这些算法的性能差异很大，这4种算法的性能差异在运行时间比较如下图所示：
下面只介绍最后两种解法的思路：
算法三：
最大子序列和可能在三处出现。或者整个出现在输入数据的左半部，后者整个出现在右部，或者跨越输入数据的中部从而位于左右两半部分之中。前两种情况可以递归求解。第三种情况的最大和可以通过求出前半部分（包含前半部分最后的一个元素）的最大和以及后半部分（同样包含最后一个元素）的最大和而得到，此时将这两个相加，从上述序列我们看到，前半部分元素的最大和是4，后半部分的最大和是7，因此横跨这两部分且通过中间的最大和为4+7=11。
| 4 | -3 | 5 | -2 | -1 | 2 | 6 | -2 |
代码:
/*解法3：用分治法，将一个数列分为2部分，时间复杂度为：O(nlogn)
* */
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 maxRightSum = maxSumRec( a, left, center );
//当最大子序列和在左边
int maxLeftSum = maxSumRec( a, center + 1, right );
//当最大子序列和出现在中间，那么最大和是左边和右边之和
int maxLeftBorderSum = 0 ;
int maxRightBorderSum = 0;
//遍历左边元素
int thisLeftMaxSum = 0;
for(int i = center; i >= left; i--){
thisLeftMaxSum += a[i];
if(thisLeftMaxSum > maxLeftBorderSum){
maxLeftBorderSum = thisLeftMaxSum;
}
}
//遍历右边的元素
int thisRightMaxSum = 0;
for(int i = center + 1; i <= right; i++){
thisRightMaxSum += a[i];
if(thisRightMaxSum > maxRightBorderSum){
maxRightBorderSum = thisRightMaxSum;
}
}
//返回三个中的最大值
return max3( maxLeftSum, maxRightSum, maxRightBorderSum + maxLeftBorderSum);
}
//程序的入口
public static int maxSubSum3(int[] a){
return maxSumRec( a, 0, a.length-1 );
}
算法四：
这种算法的具体思想是先从第一个元素逐个累加，并记录累加和同时将临时累加和大的赋给最终的最大和，如果临时累加和小于零，那么就将临时累加和置为0，从新从当前的元素的下一个元素累加。
代码：
//第三种解法,时间复杂度为O(n),但是这种解法虽然能最快的得出结果，但是过程不容易懂
public static int maxSubSum4(int[] a){
int maxSum = 0;
int thisSum = 0;
for( int j = 0; j < a.length; j++ ){
thisSum += a[j];
if(thisSum<0)
thisSum = 0;
else if(thisSum > maxSum)
maxSum = thisSum ;
}
return maxSum;
}
最后，贴出最简单，最容易想的到的方法，效率很低下！！！
/*第一种解法，时间复杂度为O(n^3)如果想要更详细的研究这个算法，可以参照wesis编写的《数据结构与算法分析- java语言描述》
* */
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;
}