前缀和

LC链接：1052.爱生气的书店老板

最终的答案是：所有可选的数+k区间内不可选的数。

而所有可选的数是固定的，不固定的是k区间内不可选的数，我们想要答案最大，只需要将k区间内不选的数最大即可。

1. 分别用两个数组，一个表示可选的数的前缀和，另外一个表示不可选的数的前缀和。
2. 枚举k区间内，可选的数+k区间内不可选的数最大。

时间复杂度$O(N)$，空间复杂度$O(N)$

AC代码

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, k;
int a[N];
LL s1[N], s2[N];

int main() {
    //读入,初始化前缀和
    cin >> n >> k;
    for (int i = 1 ; i <= n ; i ++) cin >> a[i];
    for (int i = 1 ; i <= n ; i ++) {
        int st;
        cin >> st;
        if (st) s1[i] = s1[i - 1] + a[i], s2[i] = s2[i - 1];
        else s2[i] = s2[i - 1] + a[i], s1[i] = s1[i - 1];
    }

    //枚举k区间，并更新答案
    LL res = 0;
    for (int i = 1 ; i + k - 1 <= n ; i ++) {
        int j = i + k - 1;
        res = max(res, s1[n] + s2[j] - s2[i - 1]);
    }

    cout << res << endl;


    return 0;
}