动态规划如何解决子数组问题？

本文共计5386个文字，预计阅读时间需要22分钟。

这几日刷了子数组系列的动态规划题目，在此写下这篇博客，总结记录一下做这些题目的经验，同时也对照复习。

题目一：最大子数组和 + 题目链接：53. 最大子数组和

- 解题思路： - 动态规划，维护一个当前子数组的最大和，并与全局最大和进行比较更新。 - 时间复杂度：O(n)，空间复杂度：O(1)。

- 经验总结： - 注意初始化，全局最大和初始化为0，当前子数组最大和初始化为第一个元素。 - 更新规则：如果当前子数组和大于0，则继续加入下一个元素；否则，从下一个元素开始新的子数组。 - 避免重复计算，使用一个变量存储当前子数组的最大和。

- 代码示例：pythondef maxSubArray(nums): if not nums: return 0 max_so_far=nums[0] max_ending_here=nums[0] for i in range(1, len(nums)): max_ending_here=max(nums[i], max_ending_here + nums[i]) max_so_far=max(max_so_far, max_ending_here) return max_so_far

这几天刷了子数组系列的动态规划题目，在这里写下这篇博客，总结记录一下做这些题目的经验，同时也相当于复习。

题目一：最大子数组和

题目链接：53. 最大子数组和 - 力扣（LeetCode）

当我们看完题目，看完例题之后，发现是一个动态规划的子数组问题。

那么做动态规划问题有五步

第一步：状态表示

对于这种子数组类型的题目状态表示也就是根据经验和题目要求，经验也就是以什么什么为结尾。然后根据题目要求来写状态表示

例如上面的这道题目dp[i]表示的是以i位置为结尾的所有子数组中的最大和。

第二步：根据状态表示来写状态转移方程

这里一般就可以去分析第i个元素的状态。