算法中的分而治之思想
问题引入
假设我们现在有一块长方形田地要把它分为均匀的方块且分出的方块的大小尽量的大。
问题分析
首先我们发现如果长为宽的整数倍数时，如下图我们可以将该长方形分为两个部分
如果该土地一边不是另一边的倍数时，我们可以将问题分解为如下在分割为最大后余下的那块进行同样的处理
此方法涉及到[欧几里得算法]（辗转相除法）
到此我们可以总结分而治之的思想
分解 将问题分解为一些子问题，形式相同，规模不同
解决 递归求解子问题
合并 将子问题的解组成为原问题的解
简而言之，我们就是要寻找递归条件与基本条件
我们再看一个例子关于寻找最小子数组的问题
假设要对一只股票进行分析 给出1~17天的价格，第0天的价格是每股100元，你要做的是以低价买入，高价卖出以期获得最高的收入
A[16]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}
A[1…16]的最大子数组为A[7…11]其和为43
分析：利用分治策略，我们将数组分为两个部分，就以中点为例 则最大子数组有三种情况
1、为于起点与中点之间
2、跨越中点
3、位于中点与终点之间
对于情况1，3我们可以从同一种算法，即用循环不断的判断大小
对于情况2必然是1，3两种情况的的组合，只需将1，3两种情况得到最大子数组合并即可
分解 将其分解为左数组与右数组跨越中间的仍视为左右的合并
解决 所以该条件的基本条件就是当数组只有一个时，返回它本身.其余在循环中比较即可
合并比较左边，右边以及交叉部分的大小
当然我们也可以采取暴力求解
也可以采取线性时间排序来解决
以上就不再赘述，有兴趣的可以自行了解，关键是要理解分而治之的思想
