? Editorial — Maximum Submatrix Sum (2D Kadane)

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

Олонлог эгзэ сургуулийн үйл ажиллагаа матриц хэлбэртэй:

• мөр → өдөр
• багана → анги

? Та нэг тэгш өнцөгт хэсэг сонгож ? нийлбэрийг хамгийн их болгоно

❌ 1-р санаа: Brute Force

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

• top, bottom, left, right

⏱️ O(N² × M²) → маш удаан

? 2-р санаа: Prefix Sum (2D)

2D prefix ашиглаж болно

Гэхдээ:

• Тэгш өнцөгт бүрийг шалгана
• Одоо ч O(N²M²)

? хангалтгүй

? 3-р санаа: 2D → 1D бууруулах

Энэ бол гол trick ?

Алхам:

1. top мөр сонгоно
2. bottom мөр сонгоно

? Энэ хоёрын хооронд бүх мөрийг нийлүүлнэ

? Row Compression

temp[j] = column j-ийн нийлбэр (top → bottom)

? Ингэснээр: 2D → 1D массив боллоо

? 4-р санаа: Kadane ашиглах

temp массив дээр:

? хамгийн их дэд массив = хамгийн сайн багана хэсэг

⚡ Алгоритм

for top: temp = 0 for bottom: update temp run Kadane

⏱️ Хугацаа

• O(N² × M)
• 200 × 200 → OK

? C++ код

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

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

    vector<vector<int>> a(N, vector<int>(M));

    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            cin >> a[i][j];

    long long ans = LLONG_MIN;

    for(int top = 0; top < N; top++) {
        vector<long long> temp(M, 0);

        for(int bottom = top; bottom < N; bottom++) {

            for(int j = 0; j < M; j++)
                temp[j] += a[bottom][j];

            long long cur = temp[0], best = temp[0];

            for(int j = 1; j < M; j++) {
                cur = max(temp[j], cur + temp[j]);
                best = max(best, cur);
            }

            ans = max(ans, best);
        }
    }

    cout << ans << endl;
}

? Яагаад зөв вэ?

• Бүх мөрийн хосыг шалгаж байна
• Тэр бүрт баганаар хамгийн сайн хэсгийг олж байна

? Бүх боломжит тэгш өнцөгтийг хамарна

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

1. Kadane-г сайн ойлго
2. 2D асуудлыг 1D болгох сэтгэлгээ
3. Compression trick сурах

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