动态规划 | Lune Cache

动态规划即利用历史记录来避免重复计算。思想是将原问题分解为若干子问题，即最优子结构，通过求解子问题完成对最终问题的求解；重复出现的子问题在第一次出现时对其求解，保存其结果作为历史记录从而在求解后续子问题时直接利用，完成对问题的化简。一般解决问题有三个步骤：

1. 定义一个数组保存历史记录，并确定数组所代表的含义；
 2. 确定动态转移方程，即归纳或确定出如何利用历史数据推出新的元素值，确定数组元素之间的关系式；
 3. 找到初值，归纳需要初值，历史数据也需要最根的初始值推出新值。

面对该问题，最暴力的解决方式是：时间复杂度$O(n^2)$，两层循环头尾遍历所有子序列。这样其实中间会有很多部分被重复计算累和，例如：

下标	0	1	2	3	4	5
值	-5	-3	6	4	1	-2

0~3之间的连续子数列有：0，1，2，3，(0,1)，(1,2)，(2,3)，(0,1,2)…

(0,1,2)显然需要重复计算(0,1)，也就是说其实可以直接给(0,1,2)直接提供(0,1)的运算结果或者历史记录，而不用重复这个计算过程。

如果希望进一步优化有一个时间复杂度和空间复杂度均为$O(n)$的实现，就可以考虑动态规划：

假设数组$nums$长度为$n$，下标为$0 $~$ n-1$

以$f(i)$代表以$nums[i]$为结尾的连续子数组的最大和，需要求的答案则是$max{f(i)}$，$0 \le i \le n-1$。

对于每个$f(i)$，则满足动态规划转移方程$f(i)=max{f(i-1)+nums[i],num[i]}$

$f(i)$来自==包含$nums[i]$的前$x$($ 0\le x \le i+1$)项连续数组和==或者==$nums[i]$本身==，即考虑由$nums[i]$开始一段新的子数列，或者让$nums[i]$加入$f(i-1)$对应的子数列。

动态规划的关键就在于转移方程，最大子序和问题中，$f(i)$只和$f(i-1)$相关，而$f(i)$的结果一定包含$nums[i]$，$f(i-1)$同理，保证$f(i)$的结果来自连续的某段数组，即子序列。

由思路可以得出时间复杂度为$O(n)$的算法：用$f$数组保存上述$f(i)$的值，$f(i)$由一层顺序循环和转移方程求出。