type
status
date
slug
summary
tags
category
icon
password
最近学校里有一项任务，分析一下 求解最大子序列和 的不同算法，我印象中比较好的有分治，贪心，dp，分治之前写过一篇博客，那么借着这个机会在这里记录一下这道题的贪心与dp做法。
贪心
何为贪心算法？
其本质是选择每一阶段的局部最优，从而达到全局最优。
附上维基百科的图：
对于这一道题目，体现在哪里？
这道题要求解最大连续和，我们可以将连续考虑为一个区间，每当一个区间内部的前面部分都是负数，后面都是正数，那我们的结果从正数开始计算；
比如，-7，-7，-9，200，这个区间的起始点在200，因为往前拉就会因为加上了负数而变小；
全局最优：最大连续和
局部最优：连续和为非负数，若为负数，立刻归0，因为连续和最大值不可能为负数（连续0个元素，连续和是0）
来看一下代码：
小问：
为什么要在连续和为负数时将count归0，而不是遇到遍历到的元素为负数时归0呢？
因为即使遍历到的元素为负，这个元素依旧有可能处于最大连续和的区间内部，只要连续和此时为正数，对后面添加的元素就是加成作用，就有可能处于最大连续和区间；
那连续和加上负数会不会对最后返回的结果有影响呢，万一这个负数后面跟着的正数和小与这个负数，那这个不就没成为最大连续和吗？
是的，不过不要紧，这是局部，全局最大始终是result，count只有大于result，result值才会更新。
时间复杂度：o(n)
dp
话不多说，直接上曲：
- 确定dp数组：
dp[i]为包含下表0-i的最大子序列和
- 递推公式
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
要么是之前的dp结果加上这一项，要么就是这一项；
- 初始化
dp[0]=nums[0]
- 顺序
从前往后
代码：
时间复杂度：o(n)
- 作者:Alex
- 链接:https://nextme.one/wureny.eth/article/zuidazixuliehe
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章