这道题之前我们在讲解贪心专题的时候用贪心算法解决过一次,贪心算法:最大子序和 (opens new window).
这次我们用动态规划的思路再来分析一次.
动规五部曲如下:
dp[i]:包括下标i之前的最大连续子序列和为dp[i].
dp[i]只有两个方向可以推出来:
从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态,dp[0]就是递推公式的基础.
dp[0]应该是多少呢?
在回顾一下dp[i]的定义:包括下标i之前的最大连续子序列和为dp[i].
那么我们要找最大的连续子序列,就应该找每一个i为终点的连续最大子序列.
所以在递推公式的时候,可以直接选出最大的dp[i].
以上动规五部曲分析完毕,完整代码如下:
这道题目用贪心也很巧妙,但有一点绕,需要仔细想一想,如果想回顾一下贪心就看这里吧:贪心算法:最大子序和 (opens new window)
动规的解法还是很直接的.