? Editorial — Maximum Subarray Sum with Length ≤ K

? Бодлогын товч ойлголт

Олонлог эгзэ сургуулийн бодлого:

• N өдөр байна
• Өдөр бүр оноо (эерэг / сөрөг)
• Та дараалсан хэсэг сонгоно
• Гэхдээ урт нь K-аас ихгүй

? Зорилго: хамгийн их нийлбэр

? 1-р шат: Энгийн бодолт (Brute Force)

Бүх боломжит хэсгийг шалгана:

• Эхлэл i
• Төгсгөл j (j - i + 1 ≤ K)

⏱️ Хугацаа: O(N * K)

? Том N дээр удаан

? 2-р шат: Prefix Sum

prefix[i] = a1 + a2 + ... + ai

Тэгвэл:

sum(l, r) = prefix[r] - prefix[l-1]

? 3-р шат: Бодлогыг дахин бичье

Бид maximize хийх:

prefix[r] - prefix[l-1]

гэхдээ:

r - (l-1) ≤ K
⇒ l-1 ≥ r-K

? Өөрөөр хэлбэл: prefix[r] - хамгийн бага prefix[x] (x ∈ [r-K, r-1])

? 4-р шат: Deque ашиглах

Бидэнд хэрэгтэй:

• Сүүлийн K доторх хамгийн бага prefix
• Үүнийг deque ашиглан O(1)-д олно

⚡ Алгоритм

1. prefix array бодно
2. deque-д index хадгална
3. deque нь prefix-ийн утгаар өсөх дараалалтай байна

? Алхам

i бүр дээр:

1. Хэт хуучин index (i-K) устгана
2. Хариуг update: ans = prefix[i] - min prefix
3. deque-ийг цэвэрлэнэ (том prefix устгана)
4. i-г нэмнэ

⏱️ Хугацаа

• O(N)
• IOI түвшний optimal шийдэл

? C++ код

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

int main() {
    int N, K;
    cin >> N >> K;

    vector<long long> a(N+1), prefix(N+1, 0);

    for(int i = 1; i <= N; i++) {
        cin >> a[i];
        prefix[i] = prefix[i-1] + a[i];
    }

    deque<int> dq;
    dq.push_back(0);

    long long ans = LLONG_MIN;

    for(int i = 1; i <= N; i++) {
        while(!dq.empty() && dq.front() < i - K)
            dq.pop_front();

        ans = max(ans, prefix[i] - prefix[dq.front()]);

        while(!dq.empty() && prefix[dq.back()] >= prefix[i])
            dq.pop_back();

        dq.push_back(i);
    }

    cout << ans << endl;
}

? Дүгнэлт

• Энэ бол Kadane-ийн advanced хувилбар
• Prefix sum + deque = IOI trick
• Sliding window + minimum query

? Сурагчдад өгөх зөвлөгөө

1. Kadane-г сайн ойлго
2. Prefix sum ашиглаж сур
3. Deque-г mastering хий

? Энэ бодлого = олимпиадын түвшний сэтгэлгээ ?