【转】算法导论学习笔记一分治算法

清疚 2022-11-19 12:45 243阅读 0赞

分治策略是一种常见的算法。在分治策略中，我们递归的求解一个问题，在每层递归中应用如下三个步骤： 1. 分解，将问题分解成规模更小但解决方案相同的子问题 2. 解决，递归的求解子问题，如果子问题足够小则停止递归，直接求解 3. 合并，将子问题的解组合成原问题的解

## 最大字数组问题 ##

给你一段股市的波动图，找到在什么时候买入，什么时候卖出能获得最大的收益。

### 暴力破解法 ###

我们很容易的想到一个包里破解法，就是把所有买入，卖出的组合列举出来进行对比，n天中取任意两天作为买入日和卖出日，共有n\*(n-1)/2种解法，因此这种解法的时间复杂度是O(n^2）。

### 问题变换 ###

为了方便我们处理，我们把每个数组的值变为股票的净增量。这个时候，最佳解法就变成了求一个数组的最大字数组：

### 使用分治策略的求解法 ###

我们可以认为，我们要寻找子数组array\[start,end\]的最大字数组分三种情况：

*  最大字数组在左半部分
 *  最大字数组在右半部分
 *  最大字数组起点在左半部分，终点在右半部分

对于前两种情况，我们的求解方式和分解前是相同的，我们需要单独处理第三种情况。

如图：

那么我们给出解这个问题的思路：

FindMaxCrossingSubArray(array,start,end)
    	mid=(start+end)/2
    	从mid开始向左找，找到以mid为终点的最大字数组为array[max-left,min]
    	从mid开始向右找，找到以mid为起点的最大字数组array[min,max-right]
    	跨越mid的最大字数组为array[max-left,max-right]
    	max-leftchild =FindMaxCrossingSubArray(array,start,mid)
    	max-rightchild =FindMaxCrossingSubArray(array,min,end)
    	return max-leftchild,max-rightchild,array[max-left,max-right] 3个中的最大字数组

### 分治算法分析 ###

这种方法我们需要遍历的次数会比n^2少一些，时间复杂度为O(nlgn)

## 代码实现 ##

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 </td> 
 <td> <code>public</code>&nbsp;<code>int</code><code>[] FindRecrusive(</code><code>int</code><code>[] array,&nbsp;</code><code>int</code>&nbsp;<code>low,&nbsp;</code><code>int</code>&nbsp;<code>high)</code> <code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Console.WriteLine(</code><code>"low {0}, high {1}"</code><code>, low, high);</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>(low == high)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>new</code><code>[] { low, high, array[low] };</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>mid = (low + high) / 2;</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>leftmaxsum =&nbsp;</code><code>int</code><code>.MinValue;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>currentleftsum = 0;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>leftmaxlocation = mid;</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>(</code><code>int</code>&nbsp;<code>i = mid; i &gt;= low; i--)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>currentleftsum += array[i];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>(currentleftsum &gt; leftmaxsum)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>leftmaxsum = currentleftsum;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>leftmaxlocation = i;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>rightmaxsum = 0;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>currentrightsum = 0;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>rightmaxlocation = mid;</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>(</code><code>int</code>&nbsp;<code>j = mid + 1; j &lt;= high; j++)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>currentrightsum += array[j];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>(currentrightsum &gt; rightmaxsum)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>rightmaxsum = currentrightsum;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>rightmaxlocation = j;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code><code>[] result =&nbsp;</code><code>new</code><code>[] { leftmaxlocation, rightmaxlocation, leftmaxsum + rightmaxsum };</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code><code>[] leftresult = FindRecrusive(array, 0, mid);</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>(leftresult[2] &gt; result[2])</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>result = leftresult;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code><code>[] rightresult = FindRecrusive(array, mid + 1, high);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>(rightresult[2] &gt; result[2])</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>result = rightresult;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>result;</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

自己尝试用C\#实现了下，托管在了[github][]上

[github]: https://github.com/cuicheng11165/Algorithms