利用分治法求解最大子数组和

一个数组的最大子数组和可能存在于三种情况中:

1. 该数组的左子数组中

2.该数组的右子数组中

3.可能横跨左右子数组

所以，我们可以将问题分解成一个个的子问题，其中情况1和2可用递归求解，而情况3则需要计算

s1=max{} (1 <= i <= n/2), s2=max{} （n/2+1 <= j <=n），其中情况3中s1必然包含了,

s2中必然包含了，因为情况3跨越了左右子数组。s1 + s2为情况3的最大子数组。

代码(记录了最大数组和的范围)：

/*
 * 利用分治法求最大子数组问题
 */
public class TestOne {

	public static int leftFlag;	//负责记录最大子数组和的开始下标
	public static int rightFlag; //负责记录最大子数组和的结束下标
	
	//求最大子数组跨越了两个数组的情况
	public static int midArray(int[] a,int low,int mid,int high) {
		
		// 求low...mid之间的最大数组和
		int leftSum = -10000;
		int sum = 0;
		for(int i = mid;i>=low;i--)
		{
			sum += a[i];
			if(sum > leftSum)
			{
				leftSum = sum;
				leftFlag = i;
			}
		}
		
		//求mid+1...high之间的最大数组和
		int rightSum = -10000;
		sum = 0;
		for(int i = mid+1;i<=high;i++)
		{
			sum += a[i];
			if(sum > rightSum)
			{
				rightSum = sum;
				rightFlag = i;
			}
		}
		
		return leftSum + rightSum;
	}
	
	public static int subArray(int[] a,int low,int high) {
		if(high==low)
			return a[low];
		int mid = (low + high) / 2;
		int leftSum = subArray(a,low,mid);	//求出左边数组的最大子数组和
		int rightSum = subArray(a,mid+1,high);	//求出右边数组的最大子数组和
		int midSum = midArray(a,low,mid,high);	//求出跨越左右两个数组的最大子数组和
		
		if(leftSum > rightSum && leftSum > midSum)
			return leftSum;
		else if(rightSum > leftSum && rightSum > midSum)
			return rightSum;
		else
			return midSum;
	}
	
	public static void main(String[] args) {
		int[] a = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
		
		System.out.println(subArray(a,0,a.length-1));
		System.out.println(leftFlag + "  " + rightFlag);
	}

}

代码(只计算了最大数组和，个人觉得这个更简单，更容易理解)：

public class Main {
	//分治法 最大连续和
	public static void main(String[] args) {
		int[] arr = new int[] {-1,2,1};
		int res = fun(arr,0,arr.length);
		System.out.println(res);
	}
	/**
	 * 	求arr中[low,high)的最大连续和
	 * @param arr
	 * @param low 
	 * @param high	
	 * @return
	 */
	public static int fun(int[] arr,int low,int high) {
		
		if(high-low==1)	//如果只有一个元素
			return arr[low];
		
		int mid = low + (high-low)/2;
		int maxs = max(fun(arr,low,mid),fun(arr,mid,high));	//求左区间最大连续和、右区间最大连续和，并得到两者最大值
		//求出包含arr[mid]在内的左区间的最大连续和
		int sum = 0;
		int res1 = arr[mid-1];
		for(int i = mid-1; i >= low; i--) 
			res1 = max(res1,sum+=arr[i]);
		//求出包含arr[mid]+1在内的右区间的最大连续和
		sum = 0;
		int res2 = arr[mid];
		for(int i = mid; i < high; i++)
			res2 = max(res2,sum+=arr[i]);
		
		return max(maxs,res1+res2);
	}
	
	public static int max(int x, int y) {
		return (x>y) ? x : y;
	}
}