题目大意:

给出一个有N个数字(-1000..1000,N<=10^5)的环状序列,找出一个长度不大于k的连续子序列,使其和最大。

分析:

我们可以将环状序列从某处切开,变成一行,然后复制前n-1个数字到后面,得到一个2*n-1的序列。问题即转换为在该2*n-1的序列中求长度不超过k的最大连续字段和。

预处理出前缀和,记为s。j到i的子段和即为s[i]-s[j-1]。现在只需要对每一个元素i,找出区间[i-k+1,i]中s的最小值即可。这就是一个简单的单调队列问题了。

维护一个记录s的最小值的单调队列(递增的)即可。转移是O(1)的,所以总的复杂度是O(n)的。

05-08 08:24