Minimum Sum Submatrix ในอาร์เรย์ 2 มิติ (2D Array) ใน C++

ได้รับเมทริกซ์ 2 มิติ (2D array) หาผลรวมต่ำสุดของซับเมทริกซ์ (submatrix) ใดๆ ภายในเมทริกซ์

ตัวอย่าง

Input: matrix 4×4 = {{2,3,-1,5}, {-2,9,-1,6}, {5,6,9,-9}, {-6,1,1,1}}

Output: Minimum sum submatrix in a given 2D array is: -9

คำอธิบาย: ซับเมทริกซ์ที่ให้ผลรวม -9 (อาจเป็นเซลล์เดียว -9 หรือกลุ่มเซลล์)

Input: matrix 3×3 = {{4,1,3}, {-1,-1,-1}, {6,2,3}}

Output: Minimum sum submatrix in a given 2D array is: -3

คำอธิบาย: แถวที่ 2: -1 + -1 + -1 = -3 (ซับเมทริกซ์ 1×3)

อัลกอริทึม: Kadane's Algorithm 2D (O(n³))

• 固定 left column และ right column (temp, temp_2)
• สำหรับแต่ละคู่คอลัมน์: สร้างอาร์เรย์ 1D arr[row] = ผลรวมแถวในช่วงคอลัมน์นั้น
• ใช้ Algo_Kad(arr) (Kadane แบบหา min) หาผลรวมต่ำสุดของซับอาร์เรย์ 1D นั้น
• อัปเดต global minimum
• Algo_Kad: วนคำนวณ prefix sum ถ้า sum > 0 รีเซ็ต (เพราะหา min) เก็บ min sum และตำแหน่ง

ตัวอย่างโค้ด C++

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

int Algo_Kad(int* arr, int* first, int* end, int max_size) {
    int total = 0, result = INT_MAX, temp = 0;
    *end = -1;
    for (int i = 0; i < max_size; ++i) {
        total += arr[i];
        if (total > 0) { total = 0; temp = i + 1; }
        else if (total < result) { result = total; *first = temp; *end = i; }
    }
    if (*end != -1) return result;
    result = arr[0]; *first = 0; *end = 0;
    for (int i = 1; i < max_size; i++)
        if (arr[i] < result) { result = arr[i]; *first = i; *end = i; }
    return result;
}

void Minimum_Matrix(int matrix[][column]) {
    int result = INT_MAX;
    int arr[row], total, first, end;
    for (int temp = 0; temp < column; ++temp) {
        memset(arr, 0, sizeof(arr));
        for (int temp_2 = temp; temp_2 < column; ++temp_2) {
            for (int i = 0; i < row; ++i)
                arr[i] += matrix[i][temp_2];
            total = Algo_Kad(arr, &first, &end, row);
            if (total < result) result = total;
        }
    }
    cout << "Minimum sum submatrix in a given 2D array is: " << result;
}

int main() {
    int matrix[row][column] = {
        {2, 3, -1, 5},
        {-2, 9, -1, 6},
        {5, 6, 9, -9},
        {-6, 1, 1, 1}
    };
    Minimum_Matrix(matrix);
    return 0;
}

ผลลัพธ์

Minimum sum submatrix in a given 2D array is: -9