最大子序列和

public class MaxSubsequenceSum{
	//第一种算法，时间复杂度为O(N^3)
	public int maxSubsequenceSum01(int[] array){
		int maxSum = 0 ;
		int len = array.length ;
		for (int i=0;i<len;i++) {
			for (int j=i;j<len;j++) {
				int thisSum = 0 ;
				for (int k=i;k<=j;k++) {
					thisSum += array[k] ;
				}
				if (thisSum>maxSum) {
					maxSum = thisSum ;
				}
			}
		}
		return maxSum ;
	}
	//第二种算法，时间复杂度为O(N^2)
	public int maxSubsequenceSum02(int[] array){
		int maxSum = 0 ;
		int len = array.length ;
		for (int i=0;i<len;i++) {
			int thisSum = 0 ;
			for (int j=i;j<len;j++) {
				thisSum += array[j] ;
				if (thisSum>maxSum) {
					maxSum = thisSum ;
				}
			}
		}
		return maxSum ;
	}
	//第三种算法，时间复杂度为O(NlogN)
	public int maxSubsequenceSum03(int[] array){
		return maxSubSum(array,0,array.length-1) ;
	}
	public int maxSubSum(int[] array, int left, int right){
		if(left==right){
			if (array[left]>0) {
				return array[left] ;
			}else{
				return 0 ;
			}
		}

		int center = (left+right)/2 ;
		int maxLeftSum = maxSubSum(array,left,center) ;
		int maxRightSum = maxSubSum(array,center+1,right) ;
		
		int maxLeftBorderSum = 0 ;
		int leftBorderSum = 0 ;
		for (int i=center;i>=left;i--) {
			leftBorderSum += array[i] ;
			if (leftBorderSum>maxLeftBorderSum) {
				maxLeftBorderSum = leftBorderSum ;
			}
		}
		int maxRightBorderSum = 0 ;
		int rightBorderSum = 0 ;
		for (int i=center+1;i<=right;i++) {
			rightBorderSum += array[i] ;
			if (rightBorderSum>maxRightBorderSum) {
				maxRightBorderSum = rightBorderSum ;
			}
		}
		int maxBorderSum = maxLeftBorderSum + maxRightBorderSum ;

		return Math.max(Math.max(maxLeftSum,maxRightSum),maxBorderSum) ; 
	}
	//第四种算法（联机算法），时间复杂度为O(N)
	public int maxSubsequenceSum04(int[] array){
		int thisSum = 0 ;
		int maxSum = 0 ;
		int len = array.length ;
		for (int i=0;i<len;i++) {
			thisSum += array[i]  ;

			if (thisSum>maxSum) {
				maxSum = thisSum ;
			}else if(thisSum<0){
				thisSum = 0 ;
			}
			
		}
		return maxSum ;
	}
}