我们先把问题一般化，减少限制，看看有没有什么思路。
如果不对数列长度进行任何限制，只要求选取一段连续的数，使总和最大，那么可以用动态规划解决。
用 fi 表示在前 i 个数中以 Ai 结尾的数列的最大总和，决策的时候有两种选择：要么延续前面以 Ai−1 结尾的数列，要么自己重新开始一个数列，即
fi=max{fi−1+Ai,Ai}其实也就是
fi=max{fi−1,0}+Ai最后再取 max{fi} 就是答案了，时间复杂度为 O(n) 。
如果我们现在只把 P≤k 这个限制去掉，而要求 k≤Q ，那么也并不难，用单调队列可以轻松解决。
先预处理一个前缀和数组 sum[] ，令
sumi=∑j=1iAj现在参考上面的 DP 思路。不妨依次考虑每一个 i ，让它作为所选数列的结尾。
设数列开头为 j（显然必须满足 i−j<Q ），则整个数列的和为 sumi−sumj−1 。其中 sumi 是一定的，要使和最大，必须让 sumj−1 尽可能小。
可以发现，这其实就是单调队列的经典模型，维护一个有长度限制的区间，求区间内的极值。可以在 O(n) 的时间内解决问题。
但本题不仅限制了区间的最大长度，同时还限制了最小长度，看似有点复杂，其实可以通过巧妙的方法解决这个限制。
也就是说，顺其道而行之，强制单调队列的元素队尾元素位置和 i 相差 P，使得所有元素都和 i 相差大于等于 P，这样一来就不存在区间长度的问题了。
因为这个思想比较巧妙，可以对照下面的参考代码，结合上图进行分析。
#include <algorithm> #include <climits> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <deque> using namespace std; const int MAXN = 5e5 + 100; int N, P, Q; long long W[MAXN], sum[MAXN]; deque <int> dq; int main(void) { freopen("1762.in", "r", stdin); freopen("1762.out", "w", stdout); scanf("%d%d%d", &N, &P, &Q); for (int i = 1; i <= N; i++) { scanf("%lld", &W[i]); sum[i] = sum[i - 1] + W[i]; } long long ans = LONG_LONG_MIN; dq.push_back(0); //设队首元素为 x，则区间为 (x, i] for (int i = P; i <= N; i++) { //第一个区间起码要是 (0, P]，i 要从 P 开始考虑 while (!dq.empty() && dq.front() + Q < i) dq.pop_front(); //维护上界 Q ，判断队头是否合法 while (!dq.empty() && sum[dq.back()] >= sum[i - P]) dq.pop_back(); //i-P 插入队中对应位置，维护下界 P dq.push_back(i - P); ans = max(ans, sum[i] - sum[dq.front()]); //取最优的作为答案，注意维护的是左开右闭区间，队首的值已经相当于 j-1，不要再减 1 } printf("%lld\n", ans); return 0; }其实写成两边都是闭的也可以，但是要小心 +1、-1 的地方，大小于是否要严格，以及算答案和维护队列的操作顺序，都会受到影响。
总而言之，整个程序内的含义统一就好了，个人认为不存在孰优孰劣的问题。
