算法与数据结构

分治法

分治法的思想

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

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

• 分解（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 分开，那么它的最大子数组必然属于以下三种情况之一：

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

nums[1..n]

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

明显地，如果分解数组后最大子数组完全属于左半边或完全属于右半边，可直接用递归求解，因为这两个问题仍然是最大子数组问题，只是规模更小。我们先来考虑如何处理第三种情况，该问题并不是原问题的更小规模实例，因为它多了一个限制条件——子数组必须跨越中点。为了确保我们求出的最大子数组一定跨越中点，此处分开求左半边的最大和以及右半边的最大和，然后将他们相加。

// 求解跨越中点的最大子数组
int findMaxCrossingSubArray(vector<int> nums, int low, int mid, int high) {// check left partint left_sum = INT_MIN; // maximum sum of left partint 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 partint right_sum = INT_MIN; // maximum usn of right partsum = 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<int> 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;}
}

矩阵乘法的 Strassen 算法

// TODO

代码实现

最大子数组问题

#include <iostream>
#include <vector>
#include <climits>
using namespace std;/*** @brief Find one of the maximum sum of crossing sub-array.* * @param nums * @param low * @param mid * @param high * @return int*/
int findMaxCrossingSubArray(vector<int> nums, int low, int mid, int high) {// check left partint left_sum = INT_MIN; // maximum sum of left partint 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 partint right_sum = INT_MIN; // maximum usn of right partsum = 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;
}/*** @brief Find one of the maximum sum of sub-array.* * @param nums * @param low * @param high * @return int */
int findMaxSubArray(vector<int> 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<int> nums = {-2,1,-3,4,-1,2,1,-5,4};int res = findMaxSubArray(nums, 0, nums.size()-1);cout << res << endl;return 0;
}

算法与数据结构

分治法

分治法的思想

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

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

• 分解（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 分开，那么它的最大子数组必然属于以下三种情况之一：

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

nums[1..n]

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

明显地，如果分解数组后最大子数组完全属于左半边或完全属于右半边，可直接用递归求解，因为这两个问题仍然是最大子数组问题，只是规模更小。我们先来考虑如何处理第三种情况，该问题并不是原问题的更小规模实例，因为它多了一个限制条件——子数组必须跨越中点。为了确保我们求出的最大子数组一定跨越中点，此处分开求左半边的最大和以及右半边的最大和，然后将他们相加。

// 求解跨越中点的最大子数组
int findMaxCrossingSubArray(vector<int> nums, int low, int mid, int high) {// check left partint left_sum = INT_MIN; // maximum sum of left partint 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 partint right_sum = INT_MIN; // maximum usn of right partsum = 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<int> 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;}
}

矩阵乘法的 Strassen 算法

// TODO

代码实现

最大子数组问题

#include <iostream>
#include <vector>
#include <climits>
using namespace std;/*** @brief Find one of the maximum sum of crossing sub-array.* * @param nums * @param low * @param mid * @param high * @return int*/
int findMaxCrossingSubArray(vector<int> nums, int low, int mid, int high) {// check left partint left_sum = INT_MIN; // maximum sum of left partint 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 partint right_sum = INT_MIN; // maximum usn of right partsum = 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;
}/*** @brief Find one of the maximum sum of sub-array.* * @param nums * @param low * @param high * @return int */
int findMaxSubArray(vector<int> 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<int> nums = {-2,1,-3,4,-1,2,1,-5,4};int res = findMaxSubArray(nums, 0, nums.size()-1);cout << res << endl;return 0;
}