এই টিউটোরিয়ালে, আমরা 2D ম্যাট্রিক্সে সর্বাধিক সমষ্টি আয়তক্ষেত্র খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
এই জন্য আমাদের একটি ম্যাট্রিক্স প্রদান করা হবে. আমাদের কাজ হল সাবম্যাট্রিক্সকে এর উপাদানগুলির সর্বোচ্চ যোগফল খুঁজে বের করা।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5
//returning maximum sum recursively
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;
//finding the maximum element
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
