一、问题：a[]={0,-2,11,-4,13,-5,-2}，求最大连续子序列和。二、问题分析：题目蕴涵着贪心的思想。就是选取元素的时候第一个和最后一个必须是正数，这样得到的子序列和才会是最大的。但是一味的贪心无法得到正确的结果，贪心只会求得所有正数的和，题目求的是最优解并且子问题独立，很自然而然的想到动态规划。那么这样的思想怎么表达出来呢？首先，如果前面的和加上当前选取的元素没有当前选取的元素大，那肯定不要前面的结果了吧。表达出来就是dp[j-1]+a[j]<a[j]（其中dp[j]表示前j项最大子序列和，a[j]为当前准备选取的元素。）三、状态转移方程：根据上面解释轻松可以得到(代码)
if(dp[j-1]+a[j]<a[j])dp[j]=a[j];elsedp[j]=dp[j-1]+a[j];
稍微整理下，得到动态规划的状态转移方程
dp[j]=max(dp[j-1]+a[j],a[j]);
四、子问题：前j个元素的最大子序列和。通过小问题的最优解确定大问题的最优解。五、代码展示：
#include<stdio.h>#definemax(x,y)(x)>(y)?(x):(y)inta[]={0,-2,11,-4,13,-5,-2};intdp[101];voidsolve(){intn=sizeof(a)/sizeof(a[0]);//求得数组a长度intres=a[0];//答案for(intj=1;j<=n;j++){dp[j]=max(dp[j-1]+a[j],a[j]);res=max(dp[j],res);}printf("%d\n",res);}intmain(){solve();return0;}
