总体思想：将大的拆成小的，将小的拆成更小的，一直拆分到很微量的一个状态，再研究它的效果。
分治，就是分而治之，就是把一个问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题解的合并，其中子问题的解是独立互不影响的。
在分治算法中常用递归的方式实现（也有非递归的方式），具体描述为：
①分：递归的解决较小的问题（到终止层或者可以解决的时候停下）；
②治：递归求解，如果问题够小直接求解；
③合并：将子问题的解构建父类问题。
分治与递归的区别：分治是一种思想，而递归是一种方法工具，这种方法通过自己调用自己形成一个来回的过程，而分治就是利用了多次这样来回的过程。
分治法的经典应用为快速排序、归并排序、求最近点对等。

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.        return maxSubArray3(nums,0,nums.length-1);
  4.     }
  6.     public  int maxSubArray3(int[] nums,int left,int right) {
  7.         if(left == right){
  8.             return nums[left];
  9.         }else {
  10.             int mid = (left+right)/2;
  11.             int leftMax = maxSubArray3(nums,left,mid);
  12.             int rightMax = maxSubArray3(nums,mid+1,right);
  13.             int midMax = maxSubArray3Helper(nums,left,right,mid);
  14.             if(leftMax >= rightMax && leftMax >= midMax){
  15.                 return leftMax;
  16.             }else if(rightMax >= leftMax && rightMax >= midMax){
  17.                 return rightMax;
  18.             }else {
  19.                 return midMax;
  20.             }
  21.         }
  22.     }
  23.     public  int maxSubArray3Helper(int[] nums,int left,int right,int mid) {
  24.         int leftVal = Integer.MIN_VALUE;
  25.         int rightVal = Integer.MIN_VALUE;
  26.         int sum = 0;
  27.         for(int i=mid;i>=left;i--){
  28.             sum += nums[i];
  29.             if(sum > leftVal){
  30.                 leftVal = sum;
  31.             }
  32.         }
  33.         sum = 0;
  34.         for(int j=mid+1;j<=right;j++){
  35.             sum += nums[j];
  36.             if(sum > rightVal){
  37.                 rightVal = sum;
  38.             }
  39.         }
  41.         return leftVal+rightVal;
  42.     }
  43. }

参考资料