题面:
输入一个长度为n的整数序列,从中找出一段不超过m的连续子序列使得整个序列的和最大。
最暴力的做法就是两重循环,不再赘述。
可以考虑用队列来优化。
在输入时就处理好前缀和存入数组s,利用两个变量标记队头和队尾。
利用数组q作为队列,其中存储的是下标。
从1循环到n:
先判断当前子序列长度是否大于m,如果是那么队首出队;
然后,若s[i]-s[q[head]]比当前答案大,更新答案;
接着,在队列不为空时,若s[i]<=s[q[tail]]则队尾出队;
最后,当前的i入队。
有些用词可能不恰当。