问题描述 ：

       数组 int  A[] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ; 某几个连续的子序列其和最大，比如A0+A1 = -1 。A1+A2+A3+A4 = 78 。则A1,A2,A3,A4组成的数组即是所求。

解决方案：

1.暴力求解O(n³)

　　两层for循环，指定首尾指针，再来一层for循环来计算和，然后更新最大和就行。

2.动态规划O(n)

　　动态规划的思想就是不断利用前面已经求得的结果，来计算当前的最优值。我们可以用sum[i]数组来表示，以A[i]为结尾的连续子数组的最大和。

　　可以写出转态方程大概就是：sum[i]=max(sum[i-1]+A[i],A[i]).

代码：

 

int a[NUM]={-1,-1,9,9,9,-1 ,-1, 9 };    int sum=a[0];    int res=a[0];    for (int i=1;i
     
      res)            res=sum;    }    cout<
      
       <
      
     

 

 

3.动态规划O(n)简化版

　　设sum[i]表示为以第i个元素结尾且和最大的连续子数组。假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是sum[i-1]加上这个元素，要么是只包含第i个元素，即sum[i] = max(sum[i-1] + a[i], a[i])。

　　可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可，因此算法的时间和空间复杂度都很小。（sum[i-1]+a[i]>a[i]-->sum[i-1]+a[i]-a[i]>0-->sum[i-1]>0）。

伪代码：

result = a[1]sum = a[1]for i: 2 to LENGTH[a]  if sum > 0    sum += a[i]  else    sum = a[i]  if sum > result    result = sumreturn result

 

实现：

int MaxSum(int* a,int NUM){    int sum=a[0];    int res=a[0];    for (int i=1;i
      
       0)            sum+=a[i];        else            sum=a[i];*/        sum=max(sum+a[i],a[i])        res=max(sum,res);    }    return res;  }