// base case
dp[0][0][...] = base
# 状态转移
for state1 in allOfState1:
for state2 in allOfState2:
for...
dp[state1][state2][...] = max(choose1, choose2, ...)
设计状态思路：把不确定的因素确定下来，进而把子问题定义清楚，把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题，进而把简单的问题的解组成了复杂的问题的解。
我们 不知道和最大的连续子数组一定会选哪一个数，那么我们可以求出 所有 经过输入数组的某一个数的连续子数组的最大和。
例如，示例 1 输入数组是 [-2,1,-3,4,-1,2,1,-5,4] ，我们可以求出以下子问题：
子问题 1：经过 -2 的连续子数组的最大和是多少； 子问题 2：经过 1 的连续子数组的最大和是多少； 子问题 3：经过 -3 的连续子数组的最大和是多少； 子问题 4：经过 4 的连续子数组的最大和是多少； 子问题 5：经过 -1 的连续子数组的最大和是多少； 子问题 6：经过 2 的连续子数组的最大和是多少； 子问题 7：经过 1 的连续子数组的最大和是多少； 子问题 8：经过 −5 的连续子数组的最大和是多少； 子问题 9：经过 4 的连续子数组的最大和是多少。
此时子问题的描述还有不确定的地方（这件事情叫做「有后效性」
例如「子问题 3」：经过 -3 的连续子数组的最大和是多少。
「经过 -3 的连续子数组」我们任意举出几个：
[-2,1,-3,4] ，-3 是这个连续子数组的第 3 个元素； [1,-3,4,-1] ，-3 是这个连续子数组的第 2 个元素； …… 我们不确定的是：−3 是连续子数组的第几个元素。那么我们就把 −3 定义成连续子数组的最后一个元素。在新的定义下，我们列出子问题如下：
子问题 1：以 −2 结尾的连续子数组的最大和是多少； 子问题 2：以 1 结尾的连续子数组的最大和是多少； 子问题 3：以 −3 结尾的连续子数组的最大和是多少； 子问题 4：以 4 结尾的连续子数组的最大和是多少； 子问题 5：以 −1 结尾的连续子数组的最大和是多少； 子问题 6：以 2 结尾的连续子数组的最大和是多少； 子问题 7：以 1 结尾的连续子数组的最大和是多少； 子问题 8：以 −5 结尾的连续子数组的最大和是多少； 子问题 9：以 4 结尾的连续子数组的最大和是多少。 我们加上了「结尾的」，这些子问题之间就有了联系。我们单独看子问题 1 和子问题 2：
子问题 1：以 −2 结尾的连续子数组的最大和是多少； 以 -2 结尾的连续子数组是 [-2]，因此最大和就是 −2。
子问题 2：以 1 结尾的连续子数组的最大和是多少； 以 1 结尾的连续子数组有 [-2,1] 和 [1] ，其中 [-2,1] 就是在「子问题 1」的后面加上 1 得到。-2 + 1 = -1 < 1 ，因此「子问题 2」 的答案是 1。