题意:
给出一个有 N 个数字([-1000 , 1000],N ≤ 105)的环状序列;
让你求一个和最大的连续子序列,并记录起始点。
要求这个连续子序列的长度小于等于K,加和相同的不同区间,输出起点最小的那组答案。
题解:
因为序列是环状的,所以可以在序列后面复制一段(或者复制前k - 1个数字)。
如果用sum[i]来表示复制过后的序列的前 i 个数的和;
那么任意一个子序列[i..j]的和就等于s[ j ]-s[i-1]。
对于每一个j,用s[ j ]减去最小的一个s[ i ](i ≥ j-k+1)就可以得到以 j 为终点长度不大于k的和最大的序列了。
将原问题转化为这样一个问题后,就可以用单调队列解决了。
hdu 3415"Max Sum of Max-K-sub-sequence"(单调队列)
原文:https://www.cnblogs.com/violet-acmer/p/10792796.html