問題描述

第一行有三個整數 $n$、$a$ 和 $b$，代表：

$n$：陣列的長度（元素個數）

$a$：允許的子陣列最小長度

$b$：允許的子陣列最大長度

第二行有 $n$ 個整數 $x_1$, $x_2$, …, $x_n$，代表陣列的元素。

輸出一個整數，在所有長度介於 a 到 b（含）之間的連續子陣列中，找出其元素總和最大的值。

練習題

連結：https://cses.fi/problemset/task/1644/

prefix[0] = 0

prefix[1] = x₀

prefix[2] = x₀ + x₁

prefix[3] = x₀ + x₁ + x₂

prefix[4] = x₀ + x₁ + x₂ + x₃

prefix[5] = x₀ + x₁ + x₂ + x₃ + x₄

prefix[r] - prefix[l] 代表的是陣列中從 index $l$ 到 $r-1$ 的總和

  • 若 r = 5, l = 3，prefix[r]-prefix[l]= x₃ + x₄

而我們的連續陣列長度 length 須符合 $a ≤ length ≤ b$

即 a ≤ r-1-l+1 ≤ b，為 a ≤ r-l ≤ b

因此 l 的範圍為 r-a ≥ l ≥ r-b

而我們維護的 window 代表以 r 為連續陣列尾端的所有 l 可能值，因此每當 window 繼續查找 r+1(r’) 為結尾，必須確保 r’-b-1 必須被剃除，且 r’-a 必須被加入

對每個 r 查找一次 window 內最小值相減比較最大值即可

因此時間複雜度為 $O(nlogn)$

完整程式碼

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    vector<ll> arr(n), prefix(n + 1);
    for (int i = 0; i < n; i++) cin >> arr[i];

    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }

    multiset<ll> window;
    ll mx = LLONG_MIN;

    for (int r = a; r <= n; r++) {
        if (r - b - 1 >= 0) {
            window.erase(window.find(prefix[r - b - 1]));
        }
        window.insert(prefix[r - a]);
        mx = max(mx, prefix[r] - *window.begin());
    }

    cout << mx << endl;
}