今天做https://www.acwing.com/user/myspace/collection/index/1/ 单调队列优化滑动窗口

原理详解：

1. 前缀和数组：

   • 前缀和数组 s 记录了从数组开头到当前位置的累加和。
   • s[i] 表示从数组开头到第 i 个元素的累加和。

2. 子序列和的计算：

   • 对于任意两个位置 i 和 j（i < j），子序列 [i+1, j] 的和可以通过 s[j] - s[i] 计算得到。
   • 例如，子序列 [2, 4] 的和为 s[4] - s[1]。

3. 滑动窗口和单调队列：

   • 我们使用一个单调队列来维护当前窗口内的前缀和索引。
   • 单调队列中的元素保持单调递增，这样可以保证队首元素是当前窗口内的最小前缀和。

4. 最大区间和的计算：

   • 对于每个位置 i，我们希望找到一个位置 j（i - m <= j < i），使得 s[i] - s[j] 最大。
   • 由于 s[j] 是窗口内的最小前缀和，因此 s[i] - s[j] 就是当前窗口内的最大子序列和。

具体步骤：

1. 初始化：

   • 计算前缀和数组 s。
   • 初始化单调队列 q，队列的头和尾分别为 head 和 tail。

2. 遍历数组：

   • 对于每个位置 i，检查队首元素是否在当前窗口内（即 q[head] < i - m），如果不在则移除队首元素。
   • 计算当前窗口的最大子序列和：ans = max(ans, s[i] - s[q[head]])。
   • 维护队列的单调性：在将当前索引 i 加入队列之前，移除队列尾部所有大于等于 s[i] 的元素。

cpp
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 300005;

int main() {
    int n, m;
    cin >> n >> m;
    
    int a[MAXN], s[MAXN];
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];  // 计算前缀和
    }
    
    int q[MAXN], head = 0, tail = -1;  // 模拟单调队列
    int ans = INT_MIN;
    
    for (int i = 0; i <= n; ++i) {
        // 如果队列不为空且队首元素不在当前窗口内，则移除队首元素
        if (head <= tail && q[head] < i - m) {
            head++;
        }
        
        // 计算当前窗口的最大子序列和
        if (head <= tail) {
            ans = max(ans, s[i] - s[q[head]]);
        }
        
        // 维护队列，保持队列中的前缀和索引对应的值单调递增
        while (head <= tail && s[q[tail]] >= s[i]) {
            tail--;
        }
        
        q[++tail] = i;
    }
    
    cout << ans << endl;
    
    return 0;
}