(3)分治策略

一、分治法

分治法的主要思想为将原问题转分解成几个规模较小但类似原问题的子问题，递归地求解这些子问题，然后在合并这些子问题的解来建立原问题的解。
主要分为三个步骤：

分解(Devide)——原问题分解成若干个子问题
解决(Conquer)——(递归地)求解决子问题
合并(Combine)——将子问题解合并

下面介绍一些比较常见的运用分治思想的算法。

1.归并排序

归并排序是性能比较好的一种排序方法，它的时间复杂度是O(nlgn)，是典型的运用了分治思想的算法。归并排序的步骤如下：

分解：将待排序的n个元素分解成n/2的子序列。

解决：使用归并排序递归的排列两个子序列。

合并：将两个已排序的子序列合并得出结果。

代码如下：

/**
 * @Project:
 * @description:   归并排序
 * @author: sunkang
 * @create: 2018-08-15 20:19
 * @ModificationHistory who      when       What
 **/
public class MergerSort {
    /**
     * 归并排序算法
     *分治方法核心思想为：
     *1.分解： 分解两个子数组
     *2.解决： 递归的解决两个子问题
     *3.合并： 合并两个有序的子问题的集合
     * @param A   将要排序的数组
     * @param low  数组的要排序的地位
     * @param high  数组排序的高位
     */
    public  void mergerSort(int[] A,int low ,int high ){
        if(low < high){
            //1.分解  分解两个子数组
            int mid  = (low+high)/2;
            //2.解决    递归的解决两个子问题
            mergerSort(A,low,mid);
            mergerSort(A,mid+1,high);
            //3合并    合并两个有序的子问题的集合
            merger(A,low,mid ,high);
        }
    }
    /**
     * 进行子数组合并操作
     * @param A   数组A
     * @param low  低位
     * @param mid  中位
     * @param high  高位
     */
    public  void merger(int[] A ,int low ,int mid ,int high){
        //得到子问题1的集合大小和子问题2的集合大小为n1 和n2
        int n1 = mid - low + 1;
        int n2 = high - mid;
        //创建两个临时数组,然后赋值
        int[] L = new int[n1];
        int[] R = new int[n2];
        for(int i =0;i < n1  ;i++){
            L[i]  = A[low + i];
        }
        for(int i = 0; i<n2; i++){
            R[i] = A[mid + 1 + i];
        }
        //进行两个子数组合并
        int i =0;
        int j =0;
        for(int  k = low;k<= high;k++ ){
            if(i == n1){
                A[k]  = R[j++];
            }else if( j  == n2){
                A[k]  = L[i++];
            }else if( L[i] <= R[j]){
                A[k]  = L[i++];
            }else{
                A[k]  = R[j++];
            }
        }
    }
    public void display(int[] arr){
        for(int i :arr){
            System.out.print(i+",");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        MergerSort sort  = new MergerSort() ;
        int[]  arr = new int[]{1,2,7,4,3,9};
        sort.mergerSort(arr,0,arr.length-1);
        sort.display(arr);
    }
}

下面分析一下归并排序的时间复杂度。

分解：分布步骤仅仅计算子数组的中间位置，需要常量时间，因此，D(n) = Θ(1);
解决：递归的求解两个子规模为n/2的子问题，将贡献2T(n/2)的运行时间
合并：注意一个具有n个元素的子数组上merge需要 Θ(n)的时间，所以C(n)= Θ(n);

归并排序最坏情况运行时间T(n)的递归式如下：

归并排序递归式.png

常量c代表求解规模为1的问题所需的时间以及在分解与合并步骤处理每个元素所需的时间。对T(n)进行分解可得如下的树：

归并排序的递归树图1.png

归并排序的递归图2.png

由d图可知，这棵树的高度为lg n,每层耗费cn，所以总代价为cn lg n+cn。忽略掉系数和低阶项后可知其时间复杂度为O(n lgn)。

2 最大子数组问题

题目如下：
求连续子数组的最大和
题目描述：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

目前给出三种解法：

暴力破解法
分治策略求解
线性时间求解（基于负数+任意数<任意数的思想）

代码如下,测试方法见代码最下面的main方法

/**
 * @Project:
 * @description:  最大子数组问题
 * @author:
 * @create: 2018-08-15 21:54
 * @ModificationHistory who      when       What
 **/
public class MaxArray {
    /**
     * 最大连续数组的类
     */
    class MaxSubArray{
        //连续数组的左边的下标
        int left;
        //连续数组的右边的下标
        int right;
        ////连续数组的总和
        int sum;
        @Override
        public String toString() {
            return "("+left+","+right+","+sum+")";
        }
    }

    /**
     * 方法一、暴力破解最大数组问题
     * 可以轻易得出时间复杂度为： Θ(n^2)
     * 核心思想： 选择不同的起点，遍历所有的情况，找到最大的连续数组之和
     * @param A
     * @param low
     * @param high
     * @return
     */
    public MaxSubArray findMaxSubArray_brute(int[] A,int low,int high ){
        MaxSubArray  maxSubArray  = new MaxSubArray();
        for(int i =0;i < A.length;i++){
            int sum = 0;
            for(int j =i;j<A.length;j++){
                sum = sum +A[j];
                if( sum > maxSubArray.sum){
                    maxSubArray.sum = sum;
                    maxSubArray.left = i;
                    maxSubArray.right =j;
                }

            }
        }
        return  maxSubArray;
    }


    /**
     * 方法二、通过分治法的思想来解决
     * A[low,high]的任何连续数组A[i,j]所处的位置必须是下面的情况之一
     * 1. 完全位于子数组[low,mid]中  ，因此 low<=i<=j<=mid
     * 2.完全位于子数组[mid,high]中  ，因此 mid<=i<=j<=high
     * 3.跨域中点，因此low<=i<=mid<=j<=high
     * 可以得出该方法的运行时间的递归式：
     *
     * T(n) = Θ(1)    当 n = 1;
     * T(n)= 2T（n/2）+  Θ(n)  当n>1 ;
     *
     * 由前面的归并中的分析可知时间复杂度 T(n)= Θ(n^2)
     * @param A
     * @param low
     * @param high
     * @return
     */
    public MaxSubArray  findMaxSubArray(int[] A,int low,int high){
        MaxSubArray  maxSubArray  = new MaxSubArray();
        if(low >= high){
            return  null;
        }else if(high == low  +1){//相差只有一个
            maxSubArray.left=low;
            maxSubArray.right= high;
            maxSubArray.sum = A[low];
            return  maxSubArray;
        }else{
           int mid   = (low + high)/2;
            MaxSubArray left  = findMaxSubArray(A,low,mid);
            MaxSubArray right  = findMaxSubArray(A,mid+1,high);
            MaxSubArray  cross =  findMaxSubArray_Cross(A,low,mid,high);
            if(left.sum> right.sum && left.sum>cross.sum){
                return  left;
            }else if( right.sum>left.sum &&  right.sum>cross.sum){
                return  right;
            }else{
                return  cross;
            }
        }
    }

    /**
     * 获取连续数组最大值在两边的情况
     * @param A
     * @param low
     * @param mid
     * @param high
     * @return
     */
    public MaxSubArray findMaxSubArray_Cross(int[] A, int low, int mid, int high) {
        int sum  = 0 ;
        MaxSubArray  maxSubArray  = new MaxSubArray();
        int leftMax = Integer.MIN_VALUE;
        int rightMax = Integer.MIN_VALUE;
        //获取左边的数据的最大连续的数组
        for(int i =mid ;i>= low;i--){
            sum  +=A[i];
            if( sum >leftMax){
                leftMax = sum;
                maxSubArray.left = i;
            }
        }
        sum =  0;
        //获取右边的数据的最大连续的数组
        for(int j = mid+1 ;j<high;j++){
            sum+=A[j];
            if(sum> rightMax){
                rightMax = sum;
                maxSubArray.right = j;
            }
        }
        maxSubArray.sum = leftMax+rightMax;

        return maxSubArray;
    }


    /**
     * 方法三、通过线性时间完成
     * 基本思路如下：
     * 如果a[1..j]已经得到了其最大子数组，那么a[1..j+1]最大子数组只能是两种情况
     * （1）a[1..j+1]的最大子数组就是a[1..j];
     * （2）a[1..j+1]的最大子数组是a[i..j+1],1<=i<=j;
     * 那么，如何求得所谓的（2）中的a[i..j+1]呢？
     * 首先需要承认这样的事实，如果一个数组a[p..r]求和得到负值，那么数组a[p..r+1]的最大子数组肯定不会是a[p..r+1]，因为a[p..r]+a[r+1]<a[r+1].也就是
     * 一个负数+ 任意数n< 任意数n
     * 在以下程序中，我们用temp存储所谓的a[p..r]，只要a[p..r]的求和是负值，那么从下一个a[r+1]值开始，temp重新从零开始求和，
     * 只要temp > summax,就更新summax,这样，我们一次遍历后，就能得到最大的summax
     * @return
     */
   public  MaxSubArray maxsubset(int[] a,int l,int r) {
        MaxSubArray maxSubArray  = new MaxSubArray();
        int i, temp = 0,summax = Integer.MIN_VALUE;
        for (i = l; i <= r; i++) {
            temp += a[i];
            if (temp > summax){
                summax = temp;
                maxSubArray.right = i;
            }
            if (temp < 0){
                temp = 0; //左边的数组和小于0，然后归零继续求和
                maxSubArray.left = i+1;
            }
        }
        maxSubArray.sum = summax;
        return maxSubArray;
    }


        public static void main(String[] args) {
        MaxArray maxArray  = new MaxArray();
        //1.测试暴力的情况
        int[] arr  = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
        MaxSubArray maxSubArray  =  maxArray.findMaxSubArray_brute(arr,0,arr.length-1);
        System.out.println(maxSubArray.toString());

        //测试非暴力的情况
        int[] arr1  = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
        MaxSubArray maxSubArray1  =  maxArray.findMaxSubArray(arr,0,arr.length-1);
        System.out.println(maxSubArray1.toString());

        //线性时间实现
        int[] arr2 = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
        MaxSubArray maxSubArray2=  maxArray.maxsubset(arr2,0,arr2.length-1);
        System.out.println(maxSubArray2.toString());
    }
}