इस समस्या में, हमें nXm आकार का 2-D मैट्रिक्स दिया गया है। हमारा काम n सरणियों से बढ़ते क्रम तत्वों का अधिकतम योग खोजने के लिए एक प्रोग्राम बनाना है।
कार्यक्रम विवरण - यहां, हमें प्रत्येक पंक्ति से एक तत्व को इस तरह से लेकर तत्वों का अधिकतम योग ज्ञात करने की आवश्यकता है कि ith पंक्ति का तत्व (i+1)वें पंक्ति के तत्व से कम हो। और इसी तरह। यदि ऐसी कोई राशि संभव नहीं है, तो −1 लौटाएं, जिसका अर्थ है कि कोई परिणाम संभव नहीं है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
mat[][] = {
{4, 5, 1, 3, 6},
{5, 9, 2, 7, 12},
{13, 1, 3, 6, 8},
{10, 5, 7, 2, 4}
} आउटपुट
31
स्पष्टीकरण
Taking elements from the matrix to create max Sum: 6 + 7 + 8 + 10 = 31, 6 From array 1, the maximum value. 7 from array 2, choosing 12(maximum value) cannot provide a solution. 8 from array 3, choosing 13(maximum value) cannot provide a solution. 10 From array 4, the maximum value
समाधान दृष्टिकोण
समस्या का एक समाधान यह है कि सरणियों के अंतिम सरणी से एक तत्व का चयन किया जाए और फिर दिए गए तत्व से छोटे संभावित सबसे बड़े संभावित तत्व का चयन किया जाए।
अब, इस समाधान का उपयोग करते हुए, हमारे पास एक मामला है जब इथारे (पंक्ति) में कोई तत्व नहीं है जो (i+1)वें सरणी (पंक्ति) के तत्व से कम है। यहां, हम −1 लौटेंगे।
सरणी को छाँटना हमारे समाधान की दक्षता के लिए एक अच्छी सहायता हो सकती है। जैसे कि हम बढ़ते क्रम में क्रमबद्ध करते हैं, सबसे बड़ा तत्व सूचकांक m-1 पर होगा, और अगला छोटा होगा। इसलिए, शर्त को संतुष्ट करने वाले सबसे बड़े तत्व को खोजना आसान है।
एल्गोरिदम
इनिशियलाइज़ मैक्ससम =0, currMax
चरण 1 -
Sort each array of the array of arrays (each will have elements in increasing order).
चरण 2 -
currMax = mat[n−1][m−1], the last element or the last row. Update maxSum, maxSum = currMax.
चरण 3 -
मैट्रिक्स पंक्ति के माध्यम से लूप, i =n−2 से 0.
चरण 3.1 -
Find the max element in mat[i][] which is smaller than currMax at index j.
चरण 3.2 -
if j < 0, i.e. no value found. Return −1.
चरण 3.3 -
Update currMax. currMax = mat[i][j].
चरण 3.4 -
Update maxSum, maxSum = currMax.
चरण 4 -
Return maxSum.
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <bits/stdc++.h>
#define M 5
using namespace std;
int calcMaxSumMat(int mat[][M], int n) {
for (int i = 0; i < n; i++)
sort(mat[i], mat[i] + M);
int maxSum = mat[n − 1][M − 1];
int currMax = mat[n − 1][M − 1];
int j;
for (int i = n − 2; i >= 0; i−−) {
for (j = M − 1; j >= 0; j−−) {
if (mat[i][j] < currMax) {
currMax = mat[i][j];
maxSum += currMax;
break;
}
}
if (j == −1)
return 0;
}
return maxSum;
}
int main() {
int mat[][M] = {
{4, 5, 1, 3, 6},
{5, 9, 2, 7, 12},
{12, 1, 3, 6, 8},
{10, 5, 7, 2, 4}
};
int n = sizeof(mat) / sizeof(mat[0]);
cout<<"The maximum sum of increasing order elements from n arrays is "<<calcMaxSumMat(mat, n);
return 0;
} आउटपुट
The maximum sum of increasing order elements from n arrays is 31