问题描述：给定一串整数，找出其中和最大的连续子数列，包括子数列的位置和最大和。
给定整数序列：{0, -3, 6, 8, -20, 21, 8, -9, 10, -1, 3, 6, 5}
其中和最大的连续子数列为：{21, 8, -9, 10, -1, 3, 6, 5}
【PS】
如果序列里都是负数的话，本文的算法返回最大的负数。有一种思想是，如果所有输入数据都是负数，则最大连续子数列为空，值为0，类似空集是任意集合的子集。
【暴力搜索】
依次以序列的每一个数为子数列的开头，遍历所有的情况，时间复杂度为o(n*n)。
【线性算法】
时间复杂度为o(n)。
这个算法是基于两个结论得来的。
1. 如果数列A的某个子列A(i, j) 的和S(i, j) < 0， 那么A(i, q)(q > j) 肯定不是数列A的最大递增子列。
S(i, q) =S(i, j) + S(j+1, q) < 0 + S(j+1, q) = S(j+1, q)
这个结论说明，从位置 i 开始的子列，一旦遇到和为0的子列，后面可以不搜索了，直接从 j+1 开始重新计算。
2. 如果A(i, j) 是数列A以 i 起始的子列中第一个和S(i, j) < 0 的，则对任意 i <= p <= j, p<= q，A(p, q) 的和 S(p, q) 要么小于最大连续子列和，要么与现存的最大连续子列和相等。所以A(p, q)序列可以跳过。
因为S(i ,j) 是第一个<0 的，所以S(i, p-1)必然>=0，则 S(p, q) = S(i, q) – S(i, p-1) <= S(i, q)
i p j q
—|—–|——-|——|———————
– 当 q > j 时，由结论1得知， S(i, q) < S(j+1, q)，则 S(p, q) < S(j+1, q)
i pq j
—|—–|——-|——|———————
– 当q <= j 时，（这个暂时不会证明。。。）
【分治算法】
分治算法将一个复杂的问题分解成一个个相似的简单的问题，先解决规模较小的问题，然后通过适当的组合来解决复杂的问题。特别适用于目前日渐流行的多核处理器，每个核分别同时计算小问题，再汇总结果，实现算法的并行化。
1. 规模分解
把问题的操作数集合分为2个部分，对两个子数据集合分别操作，最后进行归并。而子数据集合又可以细分成更小的数据集，用递归来实现最合适啦。
把序列 A 均分为前后两个部分 A1和A2， 假设我们已经找到了A1和A2的最大连续数列，，那么A 的最大连续数列：
– 全部在A1中
– 全部在A2中
– A1的后半部+A2的前半部
时间复杂度o(nlogn)
2. 递推式分解
实际上是数学归纳法。如果知道了规模为 n-1 的最大子数列，现在在这个子列后面多加一个蒜素，如何根据现有的结果得到规模为 n 的最大子数列。在这里，递推式分解是规模分解的一个特例，把问题分为了n-1 和 1 两个部分。也有3种情况：
– 全部在n-1的数列中
– 就是最后一个数
– n-1的数列的后缀+最后一个数
时间复杂度o(n)。
【参考】
回复里面有个很简洁的算法实现。
你是自由的，不仅是身体上的自由，
