最大连续子序列
之前讨论过该问题的一种分治算法，这里讨论基于另一种划分子问题策略的DP算法。设原数组\(L=[i_0,i_1,…,i_n]\)，函数\(F(k)\)为“\(L\)中以\(i_k\)结尾的全部连续子数组的元素值之和中的最大值”，则\(F(k)\)满足方程“\(F(k+1) = max\{ F(k) + L[k+1], L[k+1] \}\)，且\(F(0)=L[0]\)”。若解出\(F(0),F(1),..,F(n)\)，求出其中最大值即得原问题的解。该求解过程的编程实现通常是这样，先定义数组\(F[k]\)表示\(F(k)\)，从\(F[0]\)开始自低向高以数组递推并记录\(F[k]\)所有值，最后求数组\(F[k]\)的最大值即为解。算法代价为\(O(n)\)。
上述分析与解决问题的方法就是动态规划，其中关于\(F(k)\)的方程被称为动态规划的状态转移方程。该动态规划算法的代码既简短也易理解，但其实该问题本身并不特别简单，最大子数组问题最早于1977年提出，但直到1984年才被卡内基梅隆大学的教授Jay Kadane发现\(O(n)\)代价的最优算法，Kadane算法在上述动态规划的基础上进一步利用贪心策略把空间代价降为\(O(1)\)，因为该问题的状态转移不需要缓存整个\(F[k]\)。
1 2 3 4 5 6 7 8 | def dynamicProgram(arr): f = [ 0 for i in arr ] for i in range(len(arr)): if i == 0: f[0] = arr[0] else: f[i] = max(f[i-1] + arr[i] , arr[i]) return max(f) |
1 2 3 4 5 6 7 8 9 | def kadane(arr): for i in range(len(arr)): if i == 0: maximum = arr[0] cache = arr[0] else: cache = cache + arr[i] if cache + arr[i] > arr[i] else arr[i] maximum = maximum if maximum > cache else cache return maximum |