[TOC] # 最大子段和 对于一个数值序列a，定义Sum(i, j) = a\[i\] + a\[i+1\] + ... + a\[j\], (i<=j)。 则最大子段和 = Max(Sum(i, j)), (1<=i<=n, i<=j<=n) ## 例子 以[51nod-最大子段和](http://www.51nod.com/Challenge/Problem.html#!#problemId=1049)为例 ## 分析 1. 状态：f\[i\]表示以第i个元素结尾的最大子段和。 2. 转移方程：f\[i\] = max(f\[i-1\], 0) + a\[i\]。 3. 初始化：f\[i\] = a\[i\], 1 <=i <= n。 4. 答案：max(f)。 代码如下： ~~~ n = int(input()) a = [] for i in range(n):   x = int(input())   a.append(x) ​ f = [a[i] for i in range(n)] for i in range(1, n):   f[i] = max(f[i-1], 0) + a[i] print(max(f)) ~~~