给定原数组后，将其划分为 k 个子数组，使其 sum / product 最大 / 最小的 DP 类问题。 而这类问题的optimal substructure是，对于给定区间的globalMax，其最优解一定由所属区间内的 localMax 区间组成，可能不连续。 以“必须以当前结尾”来保证 local 子问题之间的连续性；用 global 来记录最优解之间可能的不连续性。

划分类DP 与 区间类DP 主要区别在于，我们只取其中 k 段，而中间部分可以留空；而区间类 DP 子问题之间是连贯而不留空的。区间类 DP 是记忆化的 divide & conquer, 划分类 DP 则是不连续 subarray 的组合，不同于区间类 DP 每一个区间都要考虑与计算，划分类DP 很多元素和子区间是可以忽略的，有贪心法的思想在里面，因此也依赖于正确的 local / global 结构来保证算法的正确性。 Kadane's Algorithm 相比 prefix sum 的特点是，必须要以 nums[0] 做初始化，从 index = 1 开始搜，优点是在处理 prefix product 的时候更容易处理好“-5” 和 “0” 的情况。 这类靠 prefix sum/product 的 subarray 问题，要注意好对于每一个子问题的 local / global 最优解结构，其中local 解都是“以当前结尾 && 连续”，而 global 未必。

DP中节省空间的办法 当dp[i]只跟dp[i-1]有关的时候，只需要用一个local var即可