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 ;	}}