Ma trận con chữ nhật diện tích lớn nhất có tổng bằng K trong C++

Cho ma trận 2D và số K. Tìm ma trận con chữ nhật có diện tích lớn nhất với tổng bằng K.

Ví dụ

Ma trận 4x4, K=9. Kết quả: Top-Left (1,0), Bottom-Right (3,2), diện tích 9.

Thuật toán: Nén cột + Tổng prefix + Hash Map

• Fix cột trái left và phải right.
• Tính mảng temp[row] = tổng hàng row từ cột left đến right.
• Trên mảng 1D temp, tìm dãy con dài nhất có tổng = K (dùng prefix sum + hash map).
• Diện tích = (right-left+1) * (down-up+1). Cập nhật max.

Triển khai C++

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

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

void maxAreaSubmatrix(vector<vector<int>>& mat, int k) {
    int R = mat.size(), C = mat[0].size();
    vector<int> temp(R), finalPt(4, 0);
    int maxArea = INT_MIN, up, down;
    
    for (int left = 0; left < C; left++) {
        fill(temp.begin(), temp.end(), 0);
        for (int right = left; right < C; right++) {
            for (int i = 0; i < R; i++) temp[i] += mat[i][right];
            if (subarraySumK(temp.data(), up, down, R, k)) {
                int area = (down - up + 1) * (right - left + 1);
                if (area > maxArea) {
                    maxArea = area;
                    finalPt = {up, down, left, right};
                }
            }
        }
    }
    
    if (maxArea == INT_MIN) { cout << "No sub-matrix found"; return; }
    cout << "(Top, Left): (" << finalPt[0] << "," << finalPt[2] << ")\n";
    cout << "(Bottom, Right): (" << finalPt[1] << "," << finalPt[3] << ")\n";
    for (int i = finalPt[0]; i <= finalPt[1]; i++) {
        for (int j = finalPt[2]; j <= finalPt[3]; j++) cout << mat[i][j] << " ";
        cout << endl;
    }
}

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

Kết quả

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

Độ phức tạp: O(C² * R) thời gian, O(R) không gian.