Hình chữ nhật lớn nhất toàn 1 trong ma trận nhị phân C++

Mô tả bài toán

Cho ma trận 2D chỉ chứa 0 và 1. Tìm hình chữ nhật con (liên tiếp) chỉ chứa 1 có diện tích lớn nhất.

Giải pháp (Histogram + Stack)

• Xử lý từng hàng như đáy của histogram: height[j] = số 1 liên tiếp lên trên kể từ hàng hiện tại.
• Với mỗi hàng, tìm diện tích hình chữ nhật lớn nhất trong histogram dùng stack đơn điệu (O(C)).
• Cập nhật kết quả toàn cục.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4

int maxHist(int row[]) {
    stack<int> result;
    int top_val, max_area = 0, area = 0, i = 0;
    while (i < C) {
        if (result.empty() || row[result.top()] <= row[i])
            result.push(i++);
        else {
            top_val = row[result.top()]; result.pop();
            area = top_val * i;
            if (!result.empty()) area = top_val * (i - result.top() - 1);
            max_area = max(max_area, area);
        }
    }
    while (!result.empty()) {
        top_val = row[result.top()]; result.pop();
        area = top_val * i;
        if (!result.empty()) area = top_val * (i - result.top() - 1);
        max_area = max(max_area, area);
    }
    return max_area;
}

int maxRectangle(int A[][C]) {
    int result = maxHist(A[0]);
    for (int i = 1; i < R; i++) {
        for (int j = 0; j < C; j++)
            if (A[i][j]) A[i][j] += A[i-1][j];
        result = max(result, maxHist(A[i]));
    }
    return result;
}

int main() {
    int A[][C] = {{0,1,1,0},{1,1,1,1},{1,1,1,1},{1,1,0,0}};
    cout << "Area of maximum rectangle is " << maxRectangle(A);
    return 0;
}

Đầu ra

Area of maximum rectangle is 8