分治算法

分冶算法的基本思想是将原问题分解为几个规模较小的但类似原问题的子问题，递归地求解这些了问题，然后再合并这些子问题的解来建立原问题的解

分冶算法在每层递归时都有三个步骤：

• 分解，原问题分为若干子问题，这些子问题都是原问题的规模较小的实例
• 解决，递归解决这些子问题，如果子问题的规模足够小，则直接求解
• 合并， 合并子问题的解成原问题的解

分治算法中需要使用递归，在使用递归时，一定要确定问题边界，即问题规模较小的条件。常见的归并排序以及求解数组中连续子数组和的最大值，都可以使用分治法解决

归并排序

归并排序的基本思想是，将数组分成两个子数组，使用递归对两个子数组进行排序，合并两个已正确排序的子数组。

注意，递归的边界条件即是，子数组中只有一个元素。假定数组中只有两个元素，分解成两个子数组，每个子数组中只有一个元素，子数组中的元素此时当然就是已经“排序正确”的，合并子数组，则整个数组已正确排序。

数组合并是整个过程中最复杂的地方。可以想象手边有两堆扑克牌，每堆扑克牌都是从小到大排序完毕，比较每堆扑克牌最上边的牌的大小，取最小的放到手上，直到有一堆扑克牌已经被取完，此时再将剩下的那一堆扑克牌全部放到手上，则手中的所有牌都是按从小到大顺序排列好。

为了界定每堆扑克牌是否已经取完，本文中向每堆扑克牌最后放入一张哨兵牌。以便于节省大量的判断，牌堆是否已经取完。

  //p是数组中合并的起始index，p是中间位置，r是末位
  public static void merge(int[] array, int p, int q, int r){
    int n1 = q - p + 1;
    int n2 = r - (q + 1) + 1;
    int[] left = new int[n1 + 1];
    int[] right = new int[n2 + 1];
    int i = 0;
    int j = 0;
    for (i = 0; i < n1; i++) {
        left[i] = array[p + i];
    }
    left[n1] = Integer.MAX_VALUE;
    for (j = 0; j < n2; j++) {
        right[j] = array[q + 1 + j];
    }
    right[n2] = Integer.MAX_VALUE;
    i = 0;
    j = 0;
    //哨兵牌为正整数最大值，所以子数组中不可能有大于它的数，假设left子数组已经被取完，只剩下哨兵牌
    //right子数组剩下的元素则必然全都小于哨兵牌，则可全取right子数组，而不用判定子数组是否已经取完
    for (int k = p; k <= r; k++) {
        if (left[i] < right[j]) {
            array[k] = left[i];
            i ++;
        }else {
            array[k] = right[j];
            j++;
        }
    }
}

最复杂的合并工作已经完成，则分解子问题和求解子问题则很简单了。

  public static void sort(int[] array, int p, int r){
    if (p < r) {
        int q = (r + p)/2;
        sort(array, p, q);
        sort(array, q + 1, r);
        merge(array, p, q, r);
    }
}

连续子数组和最大值

如果在一个数组中，找出一个连续子数组和的最大值。此问题必须是在有负数的数组中才有意义，如果数组中全为正数，那么此问题的解即为数组所有元素之和

此问题也可以用分治算法解决，将数组分解为两个子数组，那么问题的解必然为以下三个之一：

• 左子数组中的连续子数组和最大值
• 右子数组中的连续子数组和最大值
• 包含跨越分隔左右子数组的中间值的连续子数组的和的最大值。

分治算法有三步，分解子问题、解决子问题、全并子问题。本问题中，合并子问题非常简单，如果以上三个值已经求出来，通过比较大小即可得知，时间复杂度为1，分解子问题和解决子问题中只有一步较为复杂，即是上文中的第三步，求 包含中间值的连续子数组和的最大值，不过将此问题单独提出来也是比较简单的，因为此连续子数组必然包含中间值。

根据中间值将数组分成两半，分别求取左右两边的连续子数组和的最大值，再相加即可。时间复杂度为n。

  private static int[] getMaxSumSubArrayCorssMidel(int[] array, int low, int middle, int high){
    int left_sum = Integer.MIN_VALUE;
    int sum = 0;
    int maxLeftIndex = 0;
    for (int i = middle; i >= low; i--) {
        sum = sum + array[i];
        if (sum > left_sum) {
            left_sum = sum;
            maxLeftIndex = i;
        }
    }
    sum = 0;
    int right_sum = Integer.MIN_VALUE;
    int maxRightIndex = 0;
    for (int i = middle + 1; i <= high; i++) {
        sum = sum + array[i];
        if (sum > right_sum) {
            right_sum = sum;
            maxRightIndex = i;
        }
    }
    return new int[]{maxLeftIndex, maxRightIndex, left_sum + right_sum};
}

递归求解子问题的边界点是什么呢？数组只有一个元素，则连续子数组和的最大值则为数组唯一元素。确定了边界，则剩余代码非常容易写了

  private static int[] getMaxSumSubArray(int[] array, int low, int high){
    if (low == high) {
        return new int[]{low, high ,array[low]};
    }else {
        int middle = (low + high)/2;
        int[] left = getMaxSumSubArray(array, low, middle);
        int[] right = getMaxSumSubArray(array, middle + 1, high);
        int[] corss = getMaxSumSubArrayCorssMidel(array, low, middle, high);
        if (left[2] >= right[2] && left[2] >= corss[2]) {
            return left;
        }else if (right[2] >= left[2] && right[2] >= corss[2]) {
            return right;
        }else{
            return corss;
        }
    }
}

求取数组中元素的最大值

求取数组中元素的最大值也可以使用分治法解决，通常人们都使用二分法查找，后续将讨论分治算法的时间复杂度，可计算得出，二分法和分治算法的时间复杂度是一样的。不过递归本身效率不高，执行一次函数需要入栈出栈多次，分治算法的最终效率肯定是不及二分查找的。不过此文中只为展示分治算法的使用。

同理，将数组分成两个子数组，分别求取两个子数组中的最大值，再将两个子数组的最大值比较，取其大者，则可求得此问题的解。

本例中合并子问题非常简单，只需要比较子问题的解大小即可，取其大者就ok了，时间复杂度为1

  private static int findMax(int[] array, int p, int q){
    if (p == q) {
        return array[q];
    }else {
        int middle = (p + q)/2;
        int left = findMax(array, p, middle);
        int right = findMax(array, middle + 1, q);
        return (left > right) ? left : right;
    }
}

未完待续，关于分治算法的时间复杂度。