最大子序列和状态是如何确定的?

大漠刀客
  • 185

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解:
https://blog.csdn.net/qq_3834...
面介绍动态规划的做法,复杂度为 O(n)。
  步骤 1:令状态 dp[i] 表示以 A[i] 作为末尾的连续序列的最大和(这里是说 A[i] 必须作为连续序列的末尾)。
  步骤 2:做如下考虑:因为 dp[i] 要求是必须以 A[i] 结尾的连续序列,那么只有两种情况:
这个最大和的连续序列只有一个元素,即以 A[i] 开始,以 A[i] 结尾。
这个最大和的连续序列有多个元素,即从前面某处 A[p] 开始 (p<i),一直到 A[i] 结尾。
对第一种情况,最大和就是 A[i] 本身。
对第二种情况,最大和是 dp[i-1]+A[i]。
于是得到状态转移方程:
dp[i] = max{A[i], dp[i-1]+A[i]}

  这个式子只和 i 与 i 之前的元素有关,且边界为 dp[0] = A[0],由此从小到大枚举 i,即可得到整个 dp 数组。接着输出 dp[0],dp[1],...,dp[n-1] 中的最大子即为最大连续子序列的和。

**这里的解释我明白,这题难在状态的定义,明确状态定义后很容易写出转移方程。
我的问题就是,这道题的状态定义是如何想到的,怎么一步步分析出来的。(不是灵感乍现,哦,这样定义就行了)**

回复
阅读 788
1 个回答
✓ 已被采纳

这道题其实可以直接从题目提供的输入输出着手,对于输入为:[ -2, 1, -3, 4, -1, 2, 1, -5, 4 ] 的详细分析如下:

  • 对于输入为 [ -2 ] 的情况,那么结果显然是 -2
  • 对于输入为 [ -2, 1 ] 的情况,最程序化的比较当然是比较这三个结果的大小:-2-2 + 11 的大小对不对?因为从黑盒的角度上看我们并不能一眼看出结果,不过结果当然是 1
  • 对于输入为 [ -2, 1, -3 ] 的情况,我们依然像一个机器人一样列出来:-2-2 + 1-2 + 1 + (-3)11 + (-3)-3,但是我们注意到刚才列出来的情况里面:-2-2 + 11 都是 [ -2, 1 ] 里的情况,所以结论就是:求 [ -2, 1, -3 ] 的 「最大子序列和」 也就是求 [ -2, 1 ] 的 「最大子序列和」和 -3 之间的「最大子序列和」
  • ...
    根据上面推导过程中的结论我们可以把它归纳成一个状态转移方程,定义如下:

定义一个序列 S[i],存在元素为 A[i],当 i = 0 时,S[0] = A[0]
i > 0 时, S[i] = max{S[i - 1] + A[i], A[i]}

因此,我们可以把动态规化的解决思路就是找到状态转移的关系,理解为“动态规化的解决思路就是找到解决问题的规律”,这样就比较容易理解了。

宣传栏