算法与数据结构-分治法

将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤：

分解（Divide）：将原问题分解为若干子问题，这些子问题是原问题的规模较小的实例。解决（Conquer）：递归地求解这些子问题。当子问题规模足够小时，可直接求解。合并（Combine）：合并子问题的解成原问题的解。 分析分治算法

当一个算法包含对自身的递归调用时，我们往往可以用递归式来描述其运行时间。按照分治模式的三个步骤依次分析。假设 T ( n ) T(n) T(n) 是问题规模为 n n n 的一个问题的运行时间。若问题规模足够小，如对于某个常量 c c c， n ≤ c n le c n≤c，则直接求解需要常量的时间。假设把原问题分解为 a a a 个子问题，每个子问题的规模是原问题的 1 / b 1/b 1/b，则为了求解 a a a 个规模为 n / b n/b n/b 的子问题，我们需要 a T ( n / b ) aT(n/b) aT(n/b) 的时间。设分解的总时间为 D ( n ) D(n) D(n)，合并的总时间为 C ( n ) C(n) C(n)，则递归式如下：

注意：递归式可以有很多种形式。递归算法可能将问题划分为规模不等的子问题，子问题的规模也并不一定是原问题规模的固定比例（可能每次只比原问题少一个元素）。

一个经典的分治法的例子就是归并排序。

问题描述：
给定一个整数数组，找到一个具有最大和的连续子数组（最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

思路分析：
先来假设一下，如果一个数组只有一个值，那么它的最大子数组就是它自己。

nums = [n1]

如果一个数组有两个值呢？我们可以试着将它对半分，那么它的最大子数组必然存在于以下三种情况中：完全属于左半边、完全属于右半边或是跨越左右两边。具体来说，以 nums 为例，它的最大子数组必然是 [n1]、[n2] 或是 [n1, n2] 其中之一。

nums = [n1, n2] 

现在考虑一下更一般的情况，假设这个数组有 n n n 个值，我们同样可以将它对半分。假设从中间 mid 分开，那么它的最大子数组必然属于以下三种情况之一：

完全属于左半边，即存在于子数组 nums[1..mid] 中。完全属于右半边，即存在于子数组 nums[mid+1..n] 中或是跨越中间值，一部分在左半边，一部分在右半边。

nums[1..n]

因此，我们的想法就是首先分解数组，然后解决子问题，判断最大子数组究竟是三种情况中的哪一种，最后合并子问题的答案以求得原问题的答案。

明显地，如果分解数组后最大子数组完全属于左半边或完全属于右半边，可直接用递归求解。因此我们先来考虑如何处理第三种情况。
// TODO

#include 
#include 
#include 
using namespace std;


int findMaxCrossingSubArray(vector nums, int low, int mid, int high) {
    // check left part
    int left_sum = INT_MIN; // maximum sum of left part
    int sum = 0; // sum(nums[i..mid])
    for (int i=mid;i>=low;i--) {
        sum += nums[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }
    // check right part
    int right_sum = INT_MIN; // maximum usn of right part
    sum = 0; // sum(nums[mid+1..i])
    for (int i=mid+1;i<=high;i++) {
        sum += nums[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }
    return left_sum+right_sum;
}


int findMaxSubArray(vector nums, int low, int high) {

    if (low == high) {
        return nums[low];
    }

    int mid = (high-low)/2+low;
    int left_max = findMaxSubArray(nums, low, mid);
    int right_max = findMaxSubArray(nums, mid+1, high);
    int cross_max = findMaxCrossingSubArray(nums, low, mid, high);

    if (left_max>=right_max && left_max>=cross_max) {
        return left_max;
    } else if (right_max>=left_max && right_max>=cross_max) {
        return right_max;
    } else {
        return cross_max;
    }
}

// test
int main(int argc, char const *argv[]) {
    vector nums = {-2,1,-3,4,-1,2,1,-5,4};
    int res = findMaxSubArray(nums, 0, nums.size()-1);
    cout << res << endl;
    return 0;
}