Tìm ma trận con có tổng nhỏ nhất trong ma trận 2D (Minimum Sum Submatrix) trong C++

Cho ma trận 2D kích thước R×C. Tìm ma trận con (liên tiếp hàng và cột) có tổng phần tử nhỏ nhất.

Ví dụ

Đầu vào: 4x4 matrix:
{{2, 3, -1, 5}, {-2, 9, -1, 6}, {5, 6, 9, -9}, {-6, 1, 1, 1}}

Đầu ra: -9 (ma trận con 1x1 tại vị trí [2][3] giá trị -9, hoặc ma trận con lớn hơn tổng -9).

Đầu vào: 3x3 matrix:
{{4, 1, 3}, {-1, -1, -1}, {6, 2, 3}}

Đầu ra: -3 (hàng 2: -1-1-1 = -3).

Phương pháp: Kadane 2D (O(R²C) hoặc O(C²R))

• Fix cột trái L và cột phải R.
• Tính mảng temp[row] = sum(matrix[row][L..R]).
• Áp dụng Kadane 1D tìm subarray sum nhỏ nhất trên temp.
• Cập nhật kết quả toàn cục.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
const int ROW = 4, COL = 4;

int kadaneMin(int arr[], int n, int *start, int *end) {
    int sum = 0, minSum = INT_MAX, tempStart = 0;
    *end = -1;
    for (int i=0; i 0) { sum = 0; tempStart = i+1; }
        else if (sum < minSum) { minSum = sum; *start = tempStart; *end = i; }
    }
    if (*end != -1) return minSum;
    // tất cả dương: trả về phần tử nhỏ nhất
    minSum = arr[0]; *start = *end = 0;
    for (int i=1; i

Đầu ra chương trình
Minimum sum submatrix in a given 2D array is: -9