题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间负责度为O(n)。

看到这个题目，我们首先想到的是求出这个整型数组所有连续子数组的和，长度为n的数组一共有 n(n+2)/2个子数组，因此要求出这些连续子数组的和最快也需要O(n^2)的时间复杂度。但是题目要求的O(n)的时间复杂度，因此上述思路不能解决问题。

看到O(n)时间复杂度，我们就应该能够想到我们只能对整个数组进行一次扫描，在扫描过程中求出最大连续子序列和以及子序列的起点和终点位置。假如输入数组为{1,-2,3,10,-4,7,2,-5}，我们尝试从头到尾累加其中的正数，初始化和为0，第一步加上1，此时和为1，第二步加上-2，此时和为-1，第三步加上3，此时我们发现-1+3=2，最大和2反而比3一个单独的整数小，这是因为3加上了一个负数，发现这个规律以后我们就重新作出累加条件：如果当前和为负数，那么就放弃前面的累加和，从数组中的下一个数再开始计数。

代码实例：

View Code

 更正连续子序列位置错误的问题（PS:2012-8-10）

经过@Yu's 技术生涯 测试，发现我上面的代码确实存在问题，现在做了如下修改：

1. 1.添加了一个遍历用于保存遍历数组中发现的最大和的起始，原来的start和end只用于保存真是的开始于结尾。
2. 2.当currSum<0的时候，我们只让p值为最大和子数组的开始
3. 3.在最后判断currSum>greatestSum的时候，只有当currSum>greatestSum成立，才让start=p，否则就表明以p开头的子数组最大和不是最大的。

示例代码如下：

View Code

使用动态规划方法（PS：2012-10-9）

解体思路：

如果用函数f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求出max(f[0...n])。我们可以给出如下递归公式求f(i)

这个公式的意义：

1. 当以第(i-1)个数字为结尾的子数组中所有数字的和f(i-1)小于0时，如果把这个负数和第i个数相加，得到的结果反而不第i个数本身还要小，所以这种情况下最大子数组和是第i个数本身。
2. 如果以第(i-1)个数字为结尾的子数组中所有数字的和f(i-1)大于0，与第i个数累加就得到了以第i个数结尾的子数组中所有数字的和。

代码实现

View Code

其实上述两种方法的实现方式非常相似，只是解体思路不同而已。通常我们会使用递归的方式分析动态规划的问题，但是最终都会基于循环去写代码。在动态规划方法中创建了一个数组c[]用于存储中间结果，而第一种方法中只需要一个临时变量currSum.

 本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2012/05/04/2482507.html，如需转载请自行联系原作者