归并排序中我们利用了分治策略，在分治策略中，我们递归求解一个问题，在每层递归中应用如下三个步骤：

• 分解：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
• 解决：递归的求解出子问题。如果子问题的规模足够小，则停止递归，直接求解。
• 合并：将子问题的解组合成原问题的解。

当子问题足够大，需要递归求解时，称之为递归情况。当子问题变得足够小，不需要再递归时，递归已经"触底"，进入了基本情况。有时，除了与原问题形式完全一样的规模更小的子问题外，还需要求解与原问题不完全一样的子问题。这些子问题的求解看做合并步骤的一部分。

此次我们会通过最大子数组和数组最大元素两个案例来深入理解分治策略

前菜：数组最大元素问题

求解数组中最大元素的方法有很多，从分治策略的思路角度去解决问题，会有不一样的快感。

• 分解：将数组以 mid 划分为左右两个子数组，递归分解
• 解决：当数组不可分时，处理基本情况
• 合并：比较子数组返回的结果，将最大值返回。

示例代码

    private static int maxValue(int[] array,int start,int end){
        if (start==end){//数组不可分时，返回即为最大值
            return array[start];
        }
        //计算中点
        int mid = (start+end)/2;
        //递归求解左右子数组最大值
        int l = maxValue(array,start,mid);
        int r = maxValue(array,mid+1,end);
        //返回处理结果
        return l>r?l:r;
    }
复制代码

主菜：最大子数组问题

最大子数组指的是在包含负数的数组中，寻找和最大的连续子数组。（非负数整个数组就是最大的）

分析

假设寻找 A[low,high] 的最大子数组，分治策略意味着我们要将子数组划分为两个规模尽量相等的子数组。比如找到数组的中间位置 mid，然后考虑求解两个子数组 A[low,mid]，A[mid+1,high]。而 A[low,high]的任何连续子数组A[i,j]所处的位置必然是以下三种情况之一：

• 左边最大，即完全位于A[low,mid]中，low ≤ i ≤ j ≤ mid
• 右边最大，即完全位于A[mid+1,high]，mid ＜ i ≤ j ≤ high
• 跨越中点，即low ≤ i ≤ mid ＜ j ≤ high

前两种为相同形式的子问题，而对于跨越中点情况，我们需要特殊求解

跨越中点

跨越中点为特殊情况，需要额外处理：以 mid 为起始点，向左计算累加和最大元素位置，向右计算累加最大和元素位置，将元素位置与左右累加和返回。示例代码如下：

    /**
     * 计算跨越 mid 情况下的最大数组和
     *
     * @param array 待计算数组
     * @param start 起始位置
     * @param mid   中点位置
     * @param end   结束位置
     * @return int[最大子数组起始位置、最大子数组结束位置、最大子数组数值]
     */
    private static int[] maxCrossSum(int[] array, int start, int mid, int end) {
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        int rightSum = Integer.MIN_VALUE;
        int leftPos = 0, rightPos = 0;
        //计算左侧累加最大值和位置
        for (int i = mid; i >= start; i--) {
            System.out.println("array ::: " + array[i]);
            sum = sum + array[i];
            if (sum > leftSum) {
                leftSum = sum;
                leftPos = i;
            }
        }

        System.out.println("start --- mid : max left sum is " + leftSum + "; max left position is " + leftPos);

        sum = 0;
        //计算右侧累加最大值和位置
        for (int i = mid + 1; i <= end; i++) {
            System.out.println("array ::: " + array[i]);
            sum = sum + array[i];
            if (sum > rightSum) {
                rightSum = sum;
                rightPos = i;
            }
        }

        System.out.println("mid --- end : max right sum is " + rightSum + "; max right position is " + rightPos);
        //返回最大和数组
        return new int[]{leftPos, rightPos, leftSum + rightSum};
    }
复制代码

整体求解

处理好特殊情况，我们就可以按照分治策略去解决问题了。

• 分解: 以数组的中间位置划分两个子数组，递归分解问题。分别比较左边、右边、跨越中点的情况。
• 解决：当数组元素个数为1时，进入基本情况，求解问题。
• 合并：将子问题的结果合并，判断最大值并返回结果。

示例代码：

    /**
     * 对于分析中的1、2两种情况，可以通过递归拆分为相同子问题，因为都是在求指定上限（start 和 end 是确定的）的最大和子数组问题。
     * 第3种情况则特殊处理即可
     *
     * @param array 待计算数组
     * @param start 数组起始位置
     * @param end   数组结束位置
     * @return int[最大子数组起始位置、最大子数组结束位置、最大子数组数值]
     */
    private static int[] find(int[] array, int start, int end) {
        //如果数组中只有一个元素，直接返回当前元素
        if (end == start) {
            System.out.println("end == start" + start + " array value = " + array[start]);
            return new int[]{start, end, array[start]};
        }

        int mid = (start + end) / 2;
        //分别当前数组左侧最大值、右侧最大值、和包含 mid 最大值
        int[] left = find(array, start, mid);
        int[] right = find(array, mid + 1, end);
        int[] cross = maxCrossSum(array, start, mid, end);
        //比较最大值并返回
        if (left[2] > right[2] && left[2] > cross[2]) {
            return left;
        } else if (right[2] > left[2] && right[2] > cross[2]) {
            return right;
        } else {
            return cross;
        }
    }
复制代码

出差回来就开始写，终于写到了这里，哈哈哈，继续努力！下一篇《排序算法之堆排序》