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

Question

给定一个整数数组 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] 中的最大子即为最大连续子序列的和。

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

Answer 1

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

• 对于输入为 [ -2 ] 的情况，那么结果显然是 -2
• 对于输入为 [ -2, 1 ] 的情况，最程序化的比较当然是比较这三个结果的大小：-2 、 -2 + 1 和 1 的大小对不对？因为从黑盒的角度上看我们并不能一眼看出结果，不过结果当然是 1
• 对于输入为 [ -2, 1, -3 ] 的情况，我们依然像一个机器人一样列出来：-2 、 -2 + 1 、 -2 + 1 + (-3) 、 1 、 1 + (-3) 和 -3，但是我们注意到刚才列出来的情况里面：-2 、 -2 + 1 和 1 都是 [ -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]}

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