分治策略之最大子数组

柔情只为你懂 2021-06-10 20:41 394阅读 0赞

## **一、基本思想** ##

分治策略是将父问题差分成的多个子问题，然后递归的方式解决子问题。整个思想和动态规划类似，不过分治策略不要求最优解问题，而只是把父问题分解成子问题。步骤：

> 分解（Divide）

先将问题划分成子问题。子问题的形式与原问题相同。

> 解决（Conquer）

递归解决问题，当问题缩小到一定程度就能够直接求解。

> 合并（Combine）

当最小子问题解决后，递归已经触底回归，逐渐将子问题答案合并成父问题解。

## **二、事例** ##

给一个数组a\[0…n\]，假设a\[s…t\]是它的子数组，那么这个子数组的所有元素加起来最大是多少？用数学语言形式化的描述就是：求0<=s<=t<=n 使得 a\[s\]+a\[s+1\] …. + a\[t\] 最大。

**暴力求解：**  
暴力破解只需要遍历数组就能够解决：  
　　先假设最大子数组从a\[0\]开始，接下来只需要从a\[0\]开始延伸a\[0\]　 a\[0\]a\[1\]　 　a\[0\]a\[1\]a\[2\]…..  
　　再假设最大子数组从a\[1\]开始，接下来只需要从a\[1\]开始延伸a\[1\]　 a\[1\]a\[2\]　 　a\[1\]a\[2\]a\[3\]…..  
　　再假设最大子数组从a\[2\]开始，接下来只需要从a\[2\]开始延伸a\[2\]　 a\[2\]a\[3\]　 　a\[2\]a\[3\]a\[4\]…..  
　　…….如此便把所有子数组都考虑了一遍。

**分治策略：**

*Divide:*  
　　使用分治策略，我们尽量将父问题分解成规划相等的子问题。所有找到数组中间位置mid，将数组分成两个部分。即a\[low,mid\] 和 a\[mid,high\]。  
　　在考虑下答案，很明显，最后答案要不在a\[low,mid\]中，要不就在a\[mid,high\]中，或者横跨两个数组（这是答案必定包含a\[mid\]）。

*Conquer:*  
我们父问题分解成三个子问题。其中我们发现：  
　　1、求a\[low,mid\]最大子数组和和a\[mid,high\]最大子数组和其实和父问题是一样的形式，只不过规模不一样。因此这两个子问题我们只需要递归就能够求解。  
　　2、求横跨两个数组（这是答案必定包含a\[mid\]）最大子数组和问题，这个问题与父问题形式是不同的，但是这个问题有个关键因素答案必定包含a\[mid\]，因此我们只需要从a\[mid\]向两边延伸求和就能解出答案。

*Combine:*  
　　最终答案的合并就是递归的回归，从最小子问题一直回归到父问题。答案就直接解出。

*Code:*  
![这里写图片描述][20160926135119452]

> 看函数的返回值：通过if语句找出三个子问题的最大数组和再返回到父问题。是不是就是相当于把子问题的答案经过比较返回最大数组和作为父问题的最优解。该问题其实就是动态规划问题。

[20160926135119452]: /images/20210520/43b8409211de4efb8ff53a9f76b936af.png