maxsubsegment.java

最大子段和

//求最大子段和

public class MaxSubSegment {

	/*
	 * 函数一,算法时间复杂度为O(n^3),很差
	 */
	public int maxSub1(int [] a){
		
		int sum = 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>sum){ sum = thisSum; }
			}
		}
		return sum;
	}
	
	/*
	 * 函数二，算法时间复杂度为O(n^2),比一略好，但仍然很差
	 */
	public int maxSub2(int [] a){
		int sum = 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>sum){ sum = thisSum; }
			}
		}
		return sum;
	}
	
	/*
	 * 函数三，采用分治算法，算法时间复杂度为O(n*logN)，为有效算法
	 * 针对最大子段和这个具体问题本身的结构，我们还可以从算法设计的策略上对上述O(n^2)计算时间算法进行更进一步的改进。
     * 从问题的解结构也可以看出，它适合于用分治法求解。
     * 如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情况：
	 * 1. a[1:n]的最大子段和与a[1:n/2]的最大子段和相同
	 * 2. a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同
	 * 3. a[1:n]的最大子段和为a[i]+…+a[j]，并且1<=i<=n/2，n/2+1<=j<=n。
     * 对于（1）和（2）两种情况可递归求得，但是对于情况（3），容易看出a[n/2]，a[n/2+1]在最大子段中。
     * 因此，我们可以在a[1:n/2]中计算出s1=max(a[n/2]+a[n/2-1]+…+a[i]),0<=i<=n/2，
     * 并在a[n/2+1:n]中计算出s2= max(a[n/2+1]+a[n/2+2]+…+a[i])，n/2+1<=i<=n。则s1+s2为出现情况（3）的最大子段和。
     * (据此可以设计出最大子段和问题的分治算法如下：
	 */
	public int maxSub3(int [] a, int left, int right){
		int sum = 0;
		
		if(left == right){
			
			sum =a[left]>0?a[left]:0;
			
		}else{
			
			int center = (left+right)/2;
			int leftSum = maxSub3(a,left,center);
			int rightSum = maxSub3(a,center+1,right);
			
			int s1 = 0;
			int lefts = 0;
			
			//计算从a[center]开始到左边的最大值
			for(int i = center;i>=left;i--){
				 lefts += a[i];
				 if(lefts>s1) 
					 s1 = lefts;
			}
			
			int s2 = 0;
			int rights = 0;
			
			//计算从a[center+1]开始到右边的最大值
			for(int i=center+1;i<=right;i++){
				rights += a[i];
				if(rights > s2)
					s2 = rights;
			}
			
			sum = s1 + s2;
			
			if(sum < leftSum) sum = leftSum;
			if(sum < rightSum) sum = rightSum;
			
		}
		
		return sum;
	}
	
	/*
	 * 动态规划算法,amazing!!!
	 * 
	 */
	public int maxSub4(int [] a){
		
		int sum = 0;
		int b = 0;
		
		for(int i=0;i<a.length;i++){
			
			if(b>0)
				b += a[i];
			else
				b = a[i];
			
			if(b>sum) sum = b;
		}
		
		return sum;
	}
	
	public static void main(String [] args){
		
		int [] a = {12,3,1,2,3,4,-1,-2,11,-1,13,2,8,-9,12,34,33,-30,25,4,9,10};
		
		MaxSubSegment subSegment = new MaxSubSegment();
		
		//int maxSubSum = subSegment.maxSub1(a);
		
		//int maxSubSum = subSegment.maxSub2(a);
		
		//int maxSubSum = subSegment.maxSub3(a,0,a.length-1);
		
		int maxSubSum = subSegment.maxSub4(a);
		
		
		System.out.println("最大子段和："+maxSubSum);
		
	}
}