给定一个数字序列:
-2 11 -4 13 -5 -2
用d保存
求一个最大连续子序列和
这时候我们有两种方法
1.暴力破解,令两个指针分别指向头和尾然后暴力破解
2.动态规划
我们这里说动态规划
1.可分解成子问题
2.边界条件
3.转移方程 dp[i]=max(dp[i],dp[i-1]+d[i]);

dp[0]=d[0]=-2;
for(int i=1;i<6;i++)
{
    dp[i]=max(dp[i],dp[i-1]+d[i]);//这里是选当前结点和不选当前节点
}

这时候dp数组里面保存的是到i点之前的最优解

最后修改:2019 年 10 月 26 日 08 : 24 PM