एक 2D मैट्रिक्स दिया गया है, उस उपमैट्रिक्स (आयत) को ढूंढें जिसके तत्वों का योग अधिकतम हो।
यह क्लासिक कडेन के एल्गोरिदम का 2D विस्तार है।
समाधान दृष्टिकोण
- सभी बाएं कॉलम जोड़ियों (left, right) के लिए पुनरावृति करें।
- प्रत्येक जोड़ी के लिए, प्रत्येक पंक्ति का योग
temp[row]में संचित करें। - इस 1D सरणी
tempपर कडेन का एल्गोरिदम लागू करके अधिकतम योग उपसरणी खोजें। - सभी जोड़ियों के लिए अधिकतम ट्रैक करें।
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
