\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Thử từng đoạn \(k\) số và tính tổng chúng

Với mỗi tổng ta cập nhật giá trị lớn nhất nhận được

\(\color{orange}{\text{Hint 2 <Partial-sum>}}\)

• Lưu mảng tiền tố \(f[n] = f[n - 1] + a[n]\)

Từ đó ta tính được tổng của \(k\) số liên tiếp \(= a[n] + a[n - 1] + ... + a[k + 1] = (a[n] + \dots + a[1]) - (a[k] + \dots + a[1]) = f[n] - f[n - k]\)

\(\color{green}{\text{Preference AC Code }}\): Partial Sum

\(^{^{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int n = readInt();
    int k = readInt();

    vector<ll> f(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        f[i] = f[i - 1] + readInt();

    ll res = a[k];
    for (int i = k + 1; i <= n; ++i)
        res = max(res, f[i] - f[i - k]);

    cout << res;
    return 0;
}

\(\color{orange}{\text{Hint 3 <Sliding-Window>}}\)

• Mỗi khi nhận một phần tử mới ta tăng giá trị tổng lên và xóa giá trị ở ví trí trước đó \(k\) số

\(\color{green}{\text{Preference AC Code }}\): Sliding Window

\(^{^{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int n = readInt();
    int k = readInt();

    vector<int> a(n);
    for (int &x : a) getSigned(x);

    ll sum = 0;
    for (int i = 0; i < k; ++i) sum += a[i];

    ll res = sum;
    for (int i = k; i < n; ++i) res = max(res, sum += a[i] - a[i - k]);

    cout << res;
    return 0;
}

\(\color{orange}{\text{Hint 4 <STL> <Sliding-Window>}}\)

• Tương tự như trên cách tính tổng

• Trong trường hợp \(k\) rất bé so với \(n\) thì cách này giảm được nhiều không gian hơn

Mỗi khi nhận một phần tử ta đẩy nó ra sau cùng và xóa giá trị trước đó \(k\) số

\(\color{green}{\text{Preference AC Code }}\): STL, Sliding Window

\(^{^{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{time}}\ ||\ O(k)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int n = readInt();
    int k = readInt();

    ll sum = 0;
    deque<int> S;
    for (int i = 0; i < k; ++i)
    {
        S.push_back(readInt());
        sum += S.back();
    }

    ll res = sum;
    for (int i = k; i < n; ++i)
    {
        S.push_back(readInt());
        res = max(res, sum += S.back() - S.front());
        S.pop_front();
    }

    cout << res;
    return 0;
}