java-3.求子数组的最大和

package beautyOfCoding;


public class MaxSubArraySum {

	/**
	 * 3.求子数组的最大和
题目描述：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
下面的解法：数组元素全是负数时，认为子数组最大和为0
	 */
	
	public static void main(String[] args) {
		int[] a={-1,-2,-3,-10};
//		int[] a={1, -2, 3, 10, -4, 7, 2, -5};
		maxSubArraySum3(a);
		maxSubArraySum2(a);
		maxSubArraySum(a);
	}

	/*2012-07-29 编程之美书上的这个分析比较好理解，因此我写了maxSubArraySum2。其实maxSubArraySum2可以轻易地转换成maxSubArraySum。这两个方法本质是一样的。
假设A[0],A[1],...A(n-1)的最大子段为A[i],...,A[j]，则有以下3种情况
1)当0=i=j的时候，元素A[0]本身构成和最大的一段
2)当0=i<j的时候，和最大的一段以A[0]开头
3)当0<i时候，元素A[0]跟和最大的一段没有关系
Start[i]表示从第i个元素开始（包括第i个元素）的子数组和最大值，All[i]表示A[i]A[i+1]...A[n-1]这个数组的子数组和的最大值
则原始问题A[0],A[1],...A(n-1)的解All[0]=max{A[0],A[0]+Start[1],ALL[1]}
	 */
	static void maxSubArraySum2(int[] a){
		//略去参数检查
		int Start=0;
		int All=0;
		for(int i=0,len=a.length;i<len;i++){
			All=max(a[i],Start+a[i],All);
			Start=max(a[i],a[i]+Start);		//if start<0, start=a[i]
		}
		System.out.println("maxSubArraySum="+All);
	}
	
	static int max(int x,int...y){
		int max=x;
		for(int i:y){
			if(i>max){
				max=i;
			}
		}
		return max;
	}
	
	static void maxSubArraySum(int[] a){
		int len=a.length;
		int sum=0;
		int max=0;
		int lastIndex=-1;
		for(int i=0;i<len;i++){
			if(sum<=0){
				sum=a[i];
			}else{
				sum+=a[i];
			}
			if(sum>max){
				max=sum;
				lastIndex=i;
			}
		}
		System.out.println("maxSubArraySum="+max);
		if(lastIndex!=-1){
			System.out.println("and the subArray is:");
			//print the sub array
			int i=lastIndex;
			while(i>=0&&sum>=0){
				sum-=a[i];
				i--;
			}
			for(int j=i;j<=lastIndex;j++){
				System.out.print(a[j]+" ");
			}
		}
		
	}
	
	/*下面这个方法是编程之美里面在讲二维数组的子数组最大和时候提到的：
p[0]=a[0],
p[i]=p[i-1]+a[i]=a[0]+a[1]+...a[i],1<=i<=(n-1)
那么
a[i]+a[i+1]+...a[j]=p[j]-p[i-1]
子数组和最大值为max(p[j]-p[i]),0<=(i,j)<=(n-1)
	 */
	static void maxSubArraySum3(int[] a){
		//略去参数检查
		boolean allNegative=true;
		int len=a.length;
		int[] p=new int[len];
		for(int i=0;i<len;i++){
			if(allNegative){
				if(a[i]>0){
					allNegative=false;
				}
			}
			if(i==0){
				p[0]=a[0];
			}else{
				p[i]=p[i-1]+a[i];
			}
		}
		if(allNegative){
			System.out.println("maxSubArraySum=0");
		}else{
			int max=p[0];
			int min=p[0];
			for(int i=0;i<len;i++){
				if(p[i]>max){
					max=p[i];
				}
				if(p[i]<min){
					min=p[i];
				}
			}
			System.out.println("maxSubArraySum="+(max-min));
		}
		
	}
}