Hình chữ nhật có tổng lớn nhất trong ma trận 2D

Cho ma trận số nguyên (có thể âm), tìm hình chữ nhật con (submatrix) có tổng phần tử lớn nhất.

Ý tưởng: Cố định cột trái và cột phải, tính tổng từng hàng giữa hai cột đó → thành mảng 1D. Áp dụng thuật toán Kadane trên mảng 1D để tìm dãy con liên tiếp tổng max → xác định hàng trên/dưới. Lặp qua mọi cặp cột trái/phải.

Đầu vào và Đầu ra

Đầu vào: Ma trận 4x5
1   2  -1 -4 -20
-8 -3  4  2  1
3   8 10  1  3
-4 -1  1  7 -6

Đầu ra: Top-Left (1,1), Bottom-Right (3,3), Max Sum = 29
(Submatrix: hàng 1-3, cột 1-3)

Thuật toán

Kadane 1D: Tìm dãy con liên tiếp tổng max, trả về tổng và chỉ số đầu/cuối.

MaxSumRect:

1. Khởi tạo maxSum = -∞.
2. Với left từ 0 đến COL-1:
   • Khởi tạo mảng temp[ROW] = {0}.
   • Với right từ left đến COL-1:
     • Cộng M[i][right] vào temp[i] cho mọi hàng.
     • Gọi Kadane trên temp → được sum, start, end.
     • Nếu sum > maxSum → cập nhật maxSum và góc hình chữ nhật.

Ví dụ C++

#include <iostream>
#define ROW 4
#define COL 5
using namespace std;

int M[ROW][COL] = {
    {1, 2, -1, -4, -20},
    {-8, -3, 4, 2, 1},
    {3, 8, 10, 1, 3},
    {-4, -1, 1, 7, -6}
};

int kadaneAlgo(int arr[], int &start, int &end, int n) {
    int sum=0, maxSum=INT_MIN, tempStart=0; end=-1;
    for(int i=0;i<n;i++) {
        sum += arr[i];
        if(sum<0) { sum=0; tempStart=i+1; }
        else if(sum>maxSum) { maxSum=sum; start=tempStart; end=i; }
    }
    if(end!=-1) return maxSum;
    maxSum=arr[0]; start=end=0;
    for(int i=1;i<n;i++) if(arr[i]>maxSum) { maxSum=arr[i]; start=end=i; }
    return maxSum;
}

void maxSumRect() {
    int maxSum=INT_MIN, endLeft,endRight,endTop,endBottom;
    int temp[ROW], sum, start, end;
    for(int left=0;left<COL;left++) {
        for(int i=0;i<ROW;i++) temp[i]=0;
        for(int right=left;right<COL;right++) {
            for(int i=0;i<ROW;i++) temp[i] += M[i][right];
            sum = kadaneAlgo(temp,start,end,ROW);
            if(sum>maxSum) {
                maxSum=sum; endLeft=left; endRight=right; endTop=start; endBottom=end;
            }
        }
    }
    cout << "(Top, Left) (" <<endTop<<","<<endLeft<<")\n";
    cout << "(Bottom, Right) (" <<endBottom<<","<<endRight<<")\n";
    cout << "The max sum is: " << maxSum;
}

int main() { maxSumRect(); }

Kết quả

(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
The max sum is: 29