现在的位置: 首页 > 综合 > 正文

限定长度的最大子段和

2018年04月12日 ⁄ 综合 ⁄ 共 429字 ⁄ 字号 评论关闭

【题目大意】
给定一个n,m(1<=n<=1000000,1<=m<n),然后是n个数组成的序列,求长度不小于m的最大子段和;

首先不限定长度的最大子段和相信大家都会求了,无非用dp[i]表示以 a[i] 结尾的子段最大长,因此有 dp[i] = max( 0, dp[i-1] + a[i] ),然后遍历过程中维护最大值即可。

但是现在限定至少要有m长,因此我们考虑新的 max[i] 表示以 a[i] 结尾的不短于m长的最大子段和,那么因为不短于m,所以从i 往前的 m 个数必须全都要取对不对~而 i-m这个数之前的数就可以取随意长了。 i到 i-m这一段是必须要的,i-m之前的不就跟不限长的最大子段和一样了吗~

所以我们先求不限长的最大子段和 dp[i] ,遍历过程中维护 sum[i] = sum[i-1] + a[i] ,sum表示累加和,因此 i往前m长的字段和为 sum[i] - sum[i-m]。

所以有  max[i] = sum[i] - sum[i-m] + d[i-m],计算过程中维护最大值即可。

代码稍后贴上来吧。

抱歉!评论已关闭.