इस ट्यूटोरियल में, हम 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