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

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

使用动态规划方法

　　解体思路：如果用函数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个数结尾的子数组中所有数字的和。

代码实现

//使用动态规划求最大连续子数组和int FindGreatestSumOfSubArray2(int arry[],int len,int c[]) { c[0]=arry[0]; int start,end; int temp=0; int maxGreatSum=-100; for(int i=1;i
      
       maxGreatSum) { maxGreatSum=c[i]; start=temp; end=i; } } //输出c[i] for(int i=0;i
      

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