Diện tích lớn nhất ma trận con có số 1 nhiều hơn số 0 đúng 1 đơn vị trong C++

Mô tả bài toán

Cho ma trận chỉ chứa 0 và 1. Tìm ma trận con có diện tích lớn nhất sao cho số lượng 1 nhiều hơn số lượng 0 đúng 1 đơn vị.

Giải pháp (Chuyển đổi + Tổng tiền tố + Hash Map)

• Chuyển 0 → -1, 1 → 1. Bài toán thành: tìm ma trận con có tổng = 1.
• Duyệt cột trái left đến phải right:
  • Tính mảng temp[i] = tổng cột từ left đến right tại hàng i.
  • Trên mảng 1D temp, tìm mảng con dài nhất có tổng = 1 (dùng hash map lưu tổng tiền tố đầu tiên).
  • Cập nhật diện tích max = (độ dài hàng) × (số cột).

Ví dụ minh họa

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

int lenOfLongSubarr(int arr[], int n, int& start, int& finish) {
    unordered_map<int, int> um;
    int sum = 0, maxLen = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sum == 1) { start = 0; finish = i; maxLen = i + 1; }
        else if (um.find(sum) == um.end()) um[sum] = i;
        if (um.find(sum - 1) != um.end()) {
            if (maxLen < i - um[sum - 1]) {
                start = um[sum - 1] + 1;
                finish = i;
                maxLen = i - um[sum - 1];
            }
        }
    }
    return maxLen;
}

void largestSubmatrix(int mat[SIZE][SIZE], int n) {
    int finalLeft, finalRight, finalTop, finalBottom;
    int temp[n], maxArea = 0, len, start, finish;
    for (int left = 0; left < n; left++) {
        memset(temp, 0, sizeof(temp));
        for (int right = left; right < n; right++) {
            for (int i = 0; i < n; i++)
                temp[i] += mat[i][right] == 0 ? -1 : 1;
            len = lenOfLongSubarr(temp, n, start, finish);
            if (len && maxArea < (finish - start + 1) * (right - left + 1)) {
                finalLeft = left; finalRight = right;
                finalTop = start; finalBottom = finish;
                maxArea = (finish - start + 1) * (right - left + 1);
            }
        }
    }
    cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n";
    cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n";
    cout << "Maximum area: " << maxArea;
}

int main() {
    int mat[SIZE][SIZE] = {{1,0,0,1},{0,1,1,1},{1,0,0,0},{0,1,0,1}};
    int n = 4;
    largestSubmatrix(mat, n);
    return 0;
}

Đầu ra

(Top, Left): (1, 1)
(Bottom, Right): (3, 3)
Maximum area: 9