C++-এ ২D ম্যাট্রিক্স-এ সর্বোচ্চ সম রেক্ট্যাঙ্গেল (Maximum Sum Rectangle) বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি ২D ম্যাট্রিক্স দেওয়া থাকলে, এমন সাবম্যাট্রিক্স (রেক্ট্যাঙ্গেল) খুঁজে বের করতে হবে যেটির এলিমেন্টগুলোর সম সর্বোচ্চ। এটি ক্যাডেনের অ্যালগরিদম (Kadane's Algorithm) ২D-এ এক্সটেনশন।

সমাধানের পদ্ধতি

1. বাম কালাম left = 0 থেকে COL-1 পর্যন্ত লুপ।
2. দায় কালাম right = left থেকে COL-1 পর্যন্ত লুপ।
3. প্রতিটি রো-এর জন্য temp[row] += M[row][right] করে কলামের সম জমা করুন।
4. এই ১D অ্যারে temp-এ ক্যাডেনের অ্যালগরিদম চালিয়ে সর্বোচ্চ সাবঅ্যারে সম বের করুন।
5. গ্লোবাল সর্বোচ্চ আপডেট করুন এবং কোঅর্ডিনেট সংরক্ষণ করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

#define ROW 4
#define COL 5

int kadane(int* arr, int* start, int* finish, int n) {
    int sum = 0, maxSum = INT_MIN, i;
    *finish = -1;
    int local_start = 0;
    for (i = 0; i < n; ++i) {
        sum += arr[i];
        if (sum < 0) {
            sum = 0;
            local_start = i + 1;
        } else if (sum > maxSum) {
            maxSum = sum;
            *start = local_start;
            *finish = i;
        }
    }
    if (*finish != -1) return maxSum;
    maxSum = arr[0];
    *start = *finish = 0;
    for (i = 1; i < n; i++) {
        if (arr[i] > maxSum) {
            maxSum = arr[i];
            *start = *finish = i;
        }
    }
    return maxSum;
}

void findMaxSum(int M[][COL]) {
    int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;
    int left, right, i;
    int temp[ROW], sum, start, finish;
    
    for (left = 0; left < COL; ++left) {
        memset(temp, 0, sizeof(temp));
        for (right = left; right < COL; ++right) {
            for (i = 0; i < ROW; ++i)
                temp[i] += M[i][right];
            sum = kadane(temp, &start, &finish, ROW);
            if (sum > maxSum) {
                maxSum = sum;
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
            }
        }
    }
    cout << "(Top, Left) (" << finalTop << ", " << finalLeft << ")" << endl;
    cout << "(Bottom, Right) (" << finalBottom << ", " << finalRight << ")" << endl;
    cout << "Max sum is: " << maxSum << endl;
}

int main() {
    int M[ROW][COL] = {
        {1, 2, -1, -4, -20},
        {-8, -3, 4, 2, 1},
        {3, 8, 10, 1, 3},
        {-4, -1, 1, 7, -6}
    };
    findMaxSum(M);
    return 0;
}

আউটপুট

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

জটিলতা

• সময়: O(COL² × ROW)
• স্থান: O(ROW)