หา Largest Area Rectangular Sub-matrix ที่ Sum เท่ากับ K ใน C++

โจทย์: กำหนด 2D matrix และค่า K หา sub-matrix สี่เหลี่ยมที่มีพื้นที่มากที่สุด ซึ่งผลรวม elements = K

ตัวอย่าง: Matrix 4x4, K=9 → sub-matrix (1,0) ถึง (3,2) พื้นที่ 3x3=9

อัลกอริธึม: Fix Left/Right Columns + 1D Subarray Sum = K

1. Fix left column, ขยาย right column
2. สำหรับแต่ละ (left, right) คำนวณ row sums → array 1D temp[row]
3. หา longest subarray ใน temp ที่ sum = K (ใช้ prefix sum + hash map)
4. Area = (down-up+1) × (right-left+1) อัปเดต max area

ฟังก์ชัน sum_k(arr, start, end, n, k)

หา longest subarray sum = K ใน 1D array คืน start, end index ใช้ prefix sum + unordered_map

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;

bool sum_k(int arr[], int& start, int& end, int n, int k) {
    unordered_map<int, int> mp;
    int sum = 0, max_len = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sum == k) { max_len = i+1; start = 0; end = i; }
        if (mp.find(sum) == mp.end()) mp[sum] = i;
        if (mp.find(sum - k) != mp.end()) {
            if (max_len < i - mp[sum - k]) {
                max_len = i - mp[sum - k];
                start = mp[sum - k] + 1;
                end = i;
            }
        }
    }
    return max_len != 0;
}

void sum_zero(vector<vector<int>> &mat, int k) {
    int row = mat.size(), col = mat[0].size();
    int temp[row], area;
    bool found;
    int up, down;
    vector<int> final_point = {0,0,0,0};
    int maxArea = INT_MIN;
    for (int left = 0; left < col; left++) {
        memset(temp, 0, sizeof(temp));
        for (int right = left; right < col; right++) {
            for (int i = 0; i < row; i++) temp[i] += mat[i][right];
            found = sum_k(temp, up, down, row, k);
            area = (down - up + 1) * (right - left + 1);
            if (found && maxArea < area) {
                final_point = {up, down, left, right};
                maxArea = area;
            }
        }
    }
    if (final_point[0]==0 && final_point[1]==0 && final_point[2]==0 && final_point[3]==0 && mat[0][0]!=k) {
        cout << "No sub-matrix found"; return;
    }
    cout << "(Top, Left): (" << final_point[0] << ", " << final_point[2] << ")" << endl;
    cout << "(Bottom, Right): (" << final_point[1] << ", " << final_point[3] << ")" << endl;
    for (int j = final_point[0]; j <= final_point[1]; j++) {
        for (int i = final_point[2]; i <= final_point[3]; i++)
            cout << mat[j][i] << " ";
        cout << endl;
    }
}

int main() {
    vector<vector<int>> v = {
        { 2, 8, -5, 6 },
        { -7, 7, 8, -3 },
        { 11, -14, 4, 3 },
        { -4, 3, 1, 10 }
    };
    sum_zero(v, 9);
}

อินพุต

{{2,8,-5,6},{-7,7,8,-3},{11,-14,4,3},{-4,3,1,10}}, 9

เอาต์พุท

(Top, Left): (1, 0)
(Bottom, Right): (3, 2)
-7 7 8
11 -14 4
-4 3 1

Complexity

• Time: O(Col² × Row) = O(N³) สำหรับ square matrix
• Space: O(Row)