Tổng lớn nhất hình chữ nhật không vượt quá K trong C++

Cho ma trận 2D và số nguyên k. Tìm tổng lớn nhất của một hình chữ nhật con sao cho tổng ≤ k.

Ví dụ

Ma trận:

k = 3 → Hình chữ nhật xanh có tổng = 3 (tối đa).

Thuật toán: Nén cột + Prefix Sum + Set (BST)

1. Duyệt cột trái l từ 0 đến m-1.
2. Với mỗi l, duyệt cột phải r từ l đến m-1:
   • Cập nhật rowSum[i] = tổng hàng từ cột l đến r.
   • Bài toán trở thành: tìm dãy con liên tiếp trong rowSum có tổng lớn nhất ≤ k.
   • Giải bài toán con bằng prefix sum + set (cây đỏ-đen):
     • Duyệt i từ 0 đến , tính currSum.
     • Tìm trong set giá trị nhỏ nhất ≥ currSum - k (dùng lower_bound).
     • Nếu tìm thấy it, cập nhật ans = max(ans, currSum - *it).
     • Chèn currSum vào set.

Cài đặt C++

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

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int m = matrix[0].size();
        int ans = INT_MIN;
        for (int l = 0; l < m; l++) {
            vector<int> rowSum(n, 0);
            for (int r = l; r < m; r++) {
                for (int i = 0; i < n; i++) rowSum[i] += matrix[i][r];
                set<int> s;
                s.insert(0);
                int currSum = 0;
                for (int i = 0; i < n; i++) {
                    currSum += rowSum[i];
                    auto it = s.lower_bound(currSum - k);
                    if (it != s.end()) ans = max(ans, currSum - *it);
                    s.insert(currSum);
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,0,1},{0,-3,2}};
    cout << ob.maxSumSubmatrix(v, 3);
    return 0;
}

Độ phức tạp

• Thời gian: O(m^2 * n log n) — chọn cặp cột O(m^2), mỗi cặp xử lý hàng O(n log n).
• Không gian: O(n) — mảng rowSum và set.

Input / Output

Input:  [{1,0,1},{0,-3,2}] 3
Output: 3