二、算法分析之最大子序列和

最大子序列和问题的求解
  第一个算法如下，用穷举的方法求出所有的子序列和，返回最大值。

public static int maxSubSumBad(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^2),而解决该问题还有更好的办法。可以采用“分治”策略，“分”将问题分为两个大致相等的子问题，然后递归地对其分解；“治”将两个子问题的解附加到一起，最后得到整个问题的解。
  在本问题中，最大子序列和可能出现在3处，或整个出现在输入数据的左半部分，或整个出现在输入数据的右半部，或位于输入数据的中部。前两种情况可以递归求解。第三种情况可以求出前半部分的最大和以及后半部分的最大和从而得到。
  实现如下：

	public static int maxSubSum(int[] a){
		return maxSumRec(a,0,a.length-1);
	}
	
	private 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 maxInThree(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
	}
	
	public static int maxInThree(int first,int second,int third){
		int max=0;
		if(first>=second)
			max=first;
		else
			max=second;
		if(max<third)
			max=third;
		return max;
	}

  该方法的时间复杂度为O(NlogN)。而通过思考可以得到结论：如果a[i]是负的，那么它不可能是最有序列的起点，因为任何以a[i]为起点的序列都可以通过以a[i+1]作为起点得到改进。类似地，任何负的子序列不可能是最优子序列的前缀。可以写出如下方法：

	public static int maxSubSum2(int[] a){
		int maxSum=0,thisSum=0;
		for(int i=0;i<a.length;i++){
			thisSum+=a[i];
			if(maxSum<thisSum)
				maxSum=thisSum;
			else if(thisSum<0)
				thisSum=0;
		}
		return maxSum;
	}

  该算法的时间复杂度为O(N)，它只对数据进行一次扫描。在任意时刻，算法都能对它已经读入的数据给出正确答案。具有这种特性的算法叫做联机算法。