🧠 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 сурах

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