C প্রোগ্রামে দেওয়া আকারের সর্বোচ্চ যোগফলযুক্ত সাব-ম্যাট্রিক্স বের করা

ভূমিকা

একটি NxN ম্যাট্রিক্স দেওয়া থাকলে, এর মধ্যে থেকে MxM আকারের সাব-ম্যাট্রিক্স বের করতে হবে যেটির সব উপাদানের যোগফল সর্বোচ্চ। ম্যাট্রিক্সে ধনাত্মক, ঋণাত্মক ও শূন্য মান থাকতে পারে।

উদাহরণ

ইনপুট (5x5):
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
k = 2
আউটপুট:
4 4
5 5

অপ্টিমাইজড এলগরিদম (O(N²) টাইম)

প্রিফিক্স সম (prefix sum) কনসেপ্ট ব্যবহার করে কলাম-ভিত্তিক কামুলেটিভ সম বের করে, তারপর স্লাইডিং উইন্ডো দিয়ে সর্বোচ্চ যোগফল বের করা যায়।

C++ প্রোগ্রাম উদাহরণ

#include 
using namespace std;
#define SIZE 5

void maxSumSubmatrix(int arr[][SIZE], int k) {
    if (k > SIZE) return;
    int prefix[SIZE][SIZE];

    // কলাম-ভিত্তিক প্রিফিক্স সম
    for (int j = 0; j < SIZE; j++) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i][j];
        prefix[0][j] = sum;
        for (int i = 1; i < SIZE - k + 1; i++) {
            sum += (arr[i + k - 1][j] - arr[i - 1][j]);
            prefix[i][j] = sum;
        }
    }

    int maxSum = INT_MIN, *pos = NULL;
    // স্লাইডিং উইন্ডো দিয়ে সর্বোচ্চ যোগফল বের করা
    for (int i = 0; i < SIZE - k + 1; i++) {
        int sum = 0;
        for (int j = 0; j < k; j++) sum += prefix[i][j];
        if (sum > maxSum) { maxSum = sum; pos = &(arr[i][0]); }
        for (int j = 1; j < SIZE - k + 1; j++) {
            sum += (prefix[i][j + k - 1] - prefix[i][j - 1]);
            if (sum > maxSum) { maxSum = sum; pos = &(arr[i][j]); }
        }
    }

    // সাব-ম্যাট্রিক্স প্রিন্ট
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++)
            cout << *(pos + i * SIZE + j) << " ";
        cout << endl;
    }
}

int main() {
    int array[SIZE][SIZE] = {
        {1,1,1,1,1}, {2,2,2,2,2}, {3,3,3,3,3}, {4,4,4,4,4}, {5,5,5,5,5}
    };
    int k = 2;
    maxSumSubmatrix(array, k);
    return 0;
}

আউটপুট

4 4
5 5