文章来自：http://conw.net/archives/9/
（不是抄袭，那是我自己的博客，源地址查看代码有高亮）
最大连续子数列和一道很经典的算法问题，给定一个数列，其中可能有正数也可能有负数，我们的任务是找出其中连续的一个子数列（不允许空序列），使它们的和尽可能大。我们一起用多种方式，逐步优化解决这个问题。
为了更清晰的理解问题，首先我们先看一组数据：8-2 6 -1 5 4 -7 2 3第一行的8是说序列的长度是8，然后第二行有8个数字，即待计算的序列。对于这个序列，我们的答案应该是14，所选的数列是从第2个数到第5个数，这4个数的和是所有子数列中最大的。
最暴力的做法，复杂度O(N^3)暴力求解也是容易理解的做法，简单来说，我们只要用两层循环枚举起点和终点，这样就尝试了所有的子序列，然后计算每个子序列的和，然后找到其中最大的即可，C语言代码如下：
#include //N是数组长度，num是待计算的数组，放在全局区是因为可以开很大的数组int N, num[1024];int main(){ //输入数据 scanf("%d", &N); for(int i = 1; i > 1; int lans = solve(left, mid); int rans = solve(mid + 1, right); //横跨分割点的情况 int sum = 0, lmax = num[mid], rmax = num[mid + 1]; for(int i = mid; i >= left; i--) { sum += num[i]; if(sum > lmax) lmax = sum; } sum = 0; for(int i = mid + 1; i rmax) rmax = sum; } //答案是三种情况的最大值 int ans = lmax + rmax; if(lans > ans) ans = lans; if(rans > ans) ans = rans; return ans;}int main(){ //输入数据 scanf("%d", &N); for(int i = 1; i ans) ans = num[i]; } printf("%d ", ans); return 0;}
这里我们没有创建dp数组，根据递归公式的依赖关系，单独一个num数组就足以解决问题，创建一个一亿长度的数组要占用几百MB的内存！这个算法的时间复杂度是O(N)的，所以它计算一亿长度的序列也不在话下！不过你如果真的用一个这么大规模的数据来测试这个程序会很慢，因为大量的时间都耗费在程序读取数据上了！
另辟蹊径，又一个O(N)的算法考虑我们之前O(N^2)的算法，即一个简单的优化一节，我们还有没有办法优化这个算法呢？答案是肯定的！我们已知一个sum数组，sum[i]表示第1个数到第i个数的和，于是sum[j] - sum[i-1]表示第i个数到第j个数的和。那么，以第n个数为结尾的最大子序列和有什么特点？假设这个子序列的起点是m，于是结果为sum[n] - sum[m-1]。并且，sum[m]必然是sum[1],sum[2]...sum[n-1]中的最小值！这样，我们如果在维护计算sum数组的时候，同时维护之前的最小值， 那么答案也就出来了！为了节省内存，我们还是只用一个num数组。C语言代码如下：
#include //N是数组长度，num是待计算的数组，放在全局区是因为可以开很大的数组int N, num[134217728];int main(){ //输入数据 scanf("%d", &N); for(int i = 1; i ans) ans = s - m; } printf("%d ", ans); return 0;}
这个程序的原理和另辟蹊径，又一个O(N)的算法中介绍的一样，在计算前缀和的过程中维护之前得到的最小值。它的时间复杂度是O(N)，空间复杂度是O(1)，这达到了理论下限！唯一比较麻烦的是ans的初始化值，不能直接初始化为0，因为数列可能全为负数！
至此，最大连续子序列和的问题已经被我们完美解决！然而以上介绍的算法都只是直接求出问题的结果，而不能求出具体是哪一个子序列，其实搞定这个问题并不复杂，具体怎么做留待读者思考吧！