求指定长度的最大子段和

RT，给定一个整数序列，有正有负，求给定长度的最大子段和，应该怎么求啊？难道就是轮询的方式吗？

作者: lanboyj 发布时间: 2011-06-12

引用楼主 lanboyj 的回复:
RT，给定一个整数序列，有正有负，求给定长度的最大子段和，应该怎么求啊？难道就是轮询的方式吗？

如果长度给定的话，可能的字段只有n-k个。求出所有的和（注意第x位开始的字段的和可由从第x-1位开始的字段的和得到），再求最大值就行了。时间复杂度为O(n)。

作者: panghuhu250 发布时间: 2011-06-13