Maximum Sum Rectangle ใน 2D Matrix (Kadane's Algorithm 2D)

กำหนดเมทริกซ์ 2 มิติ ต้องการหา sub-rectangle (สี่เหลี่ยมผืนผ้าย่อย) ที่มีผลรวมของสมาชิกมากที่สุด

ตัวอย่าง Input และ Output

Matrix (4x5):
 1   2  -1  -4 -20
-8  -3   4   2   1
 3   8  10   1   3
-4  -1   1   7  -6

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

Submatrix:
 4  2  1
10  1  3
 1  7  -6  (Sum = 29)

อัลกอริทึม: Kadane's Algorithm ขยายเป็น 2D

แนวคิดหลัก:

1. Fix Left column และ Right column
2. สำหรับแต่ละคู่ (left, right) คำนวณผลรวมของแต่ละแถวระหว่าง left ถึง right → ได้ 1D array temp[]
3. นำ temp[] ไปหา Maximum Sum Subarray ด้วย Kadane's Algorithm → ได้ Top row และ Bottom row
4. ลองทุกคู่ (left, right) หาค่าสูงสุด

ขั้นตอนโดยละเอียด:

1. maxSum = -INF
2. for left = 0 ถึง COL-1:
   • เคลียร์ temp[ROW] = {0}
   • for right = left ถึง COL-1:
     • for แต่ละแถว i: temp[i] += M[i][right]
     • เรียก kadaneAlgorithm(temp, &start, &end, ROW)
     • ถ้าผลรวม > maxSum → อัปเดต maxSum และมุมทั้ง 4 มุม
3. แสดงผลมุมและ maxSum

Kadane's Algorithm (1D)

int kadaneAlgo(int arr[], int &start, int &end, int n) {
    int sum = 0, maxSum = INT_MIN;
    end = -1;
    int tempStart = 0;

    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;
}

ตัวอย่างโค้ด C++ สมบูรณ์

#include <iostream>
#include <climits>
#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}
};

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 << ")" << endl;
    cout << "(Bottom, Right) (" << endBottom << ", " << endRight << ")" << endl;
    cout << "The max sum is: " << maxSum;
}

int main() { maxSumRect(); return 0; }

Output

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

ความซับซ้อน

• Time: O(COL² × ROW) ≈ O(n³) สำหรับเมทริกซ์ n×n
• Space: O(ROW) - อาร์เรย์ temp