这道题我一看到，我就想到了我的最爱——贪心算法，太典型了好么。
求拥有最大和的子序列，那么秉承贪心原则，假设初始解为A[0]，那么我增加一个元素(A[1])，我就需要考虑，我的利益是多了，还是损失了。
经 @Mooophy 在 issue 里指出，下述思路并不属于贪心的范畴。荣誉属于 DP，另外得知它有一个历史名字：Kadane's algorithm.
贪心法与 DP 的最大区别在于：
- 动态规划讲究"记录历史"以及"根据历史记录做出最优选择"。
- 贪心法对历史无记录，每一次是根据 当前情况做出最优选择。
由于题意要求，子序列至少要连续，所以没可能跳过 A[1], 只有两个选择：
- A[0] + A[1]
- A[1]
说白了，就是，要么容纳新文化（改良派），要么重新开始（革命派）。哪一种可以带来最大利益，就选择哪一种。（因为人类社会也是连续的）
但这里，如果发生了革命，就会产生断链。把镜头拉远，从整条历史长河去看，每一条链子，哪一条最长呢？至少你得记录下巅峰的最大利益吧？
根据上述两条原则，我们写下了我们的算法：
benefited = max(A[i], benefited + A[i]);
maxv = max(benefited, maxv);聪明的你一定发现了，第一句条恰是当权者的决策，第二条恰是历史学家的总结。 横批：人类是贪婪的。
由于我们累计了 benefited，并根据其值进行每一次选择。故该解法的本质是 DP 而非贪心。
另外，该题下面说到 More practice， 提到要用分治法？我没什么思路，请明白者提点。
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle
咳咳咳， @Mooophy ，该出来了。。。
@Mooophy 应约而出，给出了代码，我根据其代码，尝试分析一下分治法的策略：
分治法的灵魂在于一个 "分" 字。对于这道题而言，求A的最大和子序列，可以给A来一刀：
−2,1,−3,4,−1,2,1,−5,4
left | right
crossing
由于子序列连续，它必然属于上述划分中的某一种情况：
- 完全属于 left 部分
- 完全属于 right 部分
- 属于 crossing 部分（即跨越中点）
于是其核心代码如下：
int maxSubArray(int A[], int l, int h) {
if (l == h) return A[l]; // 仅有一个数
int m = (l + h) / 2; // 中点位置(划分点)
return std::max({maxSubArray(A, l, m), maxSubArray(A, m+1, h), maxCrossing(A, l, m, h)});
}是否非常的简洁呢？
下面问题集中在 maxCrossing 的策略，这个过程可以线性求出。即将其属于 left 范畴的 sum 与属于 right 范畴的 sum 加起来即可。
实现代码请见：divide_conquer.h
这部分的详细思路可参考 CLRS 的第四章分治法的第一小节。