ผลรวมสี่เหลี่ยมผืนผ้าสูงสุดไม่เกิน K ใน C++

ภาพรวมปัญหา

ให้เมทริกซ์ 2D และจำนวนเต็ม k หาผลรวมของสี่เหลี่ยมผืนผ้าย่อย (submatrix) ที่มากที่สุด แต่ไม่เกิน k

ตัวอย่าง

Matrix = [[1,0,1],[0,-3,2]], k = 3
สี่เหลี่ยมที่ทำเครื่องหมาย: คอลัมน์ 3 (index 2) ทั้ง 2 แถว → 1 + 2 = 3
Output: 3

วิธีแก้ปัญหา: Prefix Sum + BST (Set)

ลดปัญหา 2D เหลือ 1D โดย固定คอลัมน์ซ้าย (l) และขวา (r) แล้วคำนวณผลรวมแถว (rowSum) สำหรับช่วงคอลัมน์นั้น แล้วหา subarray ผลรวมสูงสุด ≤ k ด้วย Set

ขั้นตอนหลัก

วน l = 0 ถึง m-1 (คอลัมน์ซ้าย)
สร้าง rowSum[n] = 0
วน r = l ถึง m-1 (คอลัมน์ขวา):
- อัปเดต rowSum[i] += matrix[i][r]
- หา subarray ของ rowSum ที่ผลรวม ≤ k สูงสุด:
  - ใช้ set เก็บ prefix sums
  - วนคำนวณ currSum สะสม
  - หา it = s.lower_bound(currSum - k) (ค่า ≥ currSum - k ที่น้อยที่สุด)
  - ถ้าเจอ → ans = max(ans, currSum - *it)
  - เพิ่ม currSum เข้า set

โค้ด 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);
            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));
}

การวิเคราะห์ความซับซ้อน

เวลา: O(m² × n log n) — m = คอลัมน์, n = แถว
พื้นที่: O(n) — rowSum และ set