动态规划

算法

典型例题

最大字段和

对于全是非正数的序列，答案明显就是其中的最大元素

对于有正数的序列，考虑以每一个点为结尾的最大字段和，这个子段一定满足前缀和均非负，因为如果有一个前缀是负的，那么去掉这个前缀对于这个点一定更优，并且这个子段要尽量往前延伸

所以我们可以只用一次扫描，记录目前统计的和sum 以及答案 ans. 当 sum 加上当前位置这个数还是正数的时候就继续累加sum, 否则就将sum 置为 0.：这样就舍掉了所有前缀为负的情况，并且保证了这个子段尽可能的长，也就是说扫描中记录的sum就是以每个点为结尾的最大字段和，每一次如果sum比ans大就可以更新ans. 最后 ans就是整体的最大子段和。

时间复杂度 O(N)