算法导论第四章分治的第一个例题：最大子数组问题
$O(n^2)$
暴力算法
$O(nlogn)$
分治算法
将数组array[low..high]分为array[low..mid]，array[mid+1..high]
最大子数组array[i..j]所在位置必然在如下三种情况里：
1.完全位于array[low..mid]
2.完全位于array[mid+1..high]
3.跨越mid （low<i<mid<j<high)
1,2为重复子问题
3即寻找i，j使array[i..mid]，array[mid+1..j]分别最大 ： O(n)级别
递归方程：
$$T(n)=2*T(n/2)+O(n)$$
复杂度即$O(nlogn)$
$O(n)$
线性算法
推荐一个非常棒的博客：最大子数组的和问题–线性算法