分析
这里我们以数组 arr[]={-20,11,-4,13,-5,-2}; 为例
求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间[start, end]只可能有以下三种可能性:
在[0, (arr.length-1)/2]这个区域内
在[(arr.length-1)/2+1, arr.length-1]这个区域内
起点位于[0, (arr.length-1)/2],终点位于[(arr.length-1)/2+1, arr.length-1]内
以上三种情形的最大者，即为所求. 前两种情形符合子问题递归特性，所以递归可以求出. 对于第三种情形，则需要单独处理. 第三种情形必然包括了 (arr.length-1)/2 和 (arr.length-1)/2+1 两个位置，这样就可以利用第二种穷举的思路求出:
1. 以(arr.length-1)/2为终点，往左移动扩张，求出和最大的一个leftSum
2. 以(arr.length-1)/2+1为起点，往右移动扩张，求出和最大的一个rightSum
3. leftSum+rightSum=midSum midSum是第三种情况可能的最大值
//最大子段 public class Maxsize { public static void main(String[] args) { int arr[]={-20,11,-4,13,-5,-2}; System.out.println(maxsize(arr,0,arr.length-1)); } public static int maxsize(int[] arr, int left, int right){ int sum=0,midSum=0,leftSum=0,rightSum=0; int center,s1,s2,lefts,rights; //如果序列长度为1时 if (left==right){ sum=arr[left]; } else { //划分 center=(left+right)/2; //左递归 leftSum=maxsize(arr,left,center); //又递归 rightSum=maxsize(arr,center+1,right); s1=0;lefts=0; for (int i=center;i>=left;i--){ lefts+=arr[i]; if (lefts>s1){ s1=lefts; } } s2=0;rights=0; for (int j=center+1;j<=right;j++){ rights+=arr[j]; if (rights>s2){ s2=rights; } } midSum=s1+s2; if (midSum<leftSum){ sum=leftSum; } else { sum=midSum; } if (sum<rightSum){ sum=rightSum; } } return sum; } }
