इस समस्या में, हमें n×m आकार का एक 2-D मैट्रिक्स दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो n सरणियों से बढ़ते क्रम के तत्वों का अधिकतम योग ढूंढे।
प्रोग्राम विवरण
यहां, हमें प्रत्येक पंक्ति से एक तत्व लेकर तत्वों का अधिकतम योग ढूंढना है ताकि iवीं पंक्ति का तत्व (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
व्याख्या
मैट्रिक्स से तत्व लेकर अधिकतम योग बनाना: 6 + 7 + 8 + 10 = 31 सरणी 1 से 6, अधिकतम मान। सरणी 2 से 7, 12 (अधिकतम मान) चुनने से समाधान नहीं मिलता। सरणी 3 से 8, 13 (अधिकतम मान) चुनने से समाधान नहीं मिलता। सरणी 4 से 10, अधिकतम मान।
समाधान दृष्टिकोण
समस्या का एक समाधान सरणियों की सरणी की अंतिम सरणी से एक तत्व चुनकर और फिर ऊपर जाते हुए दिए गए तत्व से छोटे सबसे बड़े संभावित तत्व को चुनना है।
अब, इस समाधान का उपयोग करके, हमारे पास एक मामला है जब iवीं सरणी (पंक्ति) में कोई तत्व नहीं है जो (i+1)वीं सरणी (पंक्ति) के तत्व से छोटा हो। यहां, हम -1 वापस करेंगे।
सरणी को क्रमबद्ध करना हमारे समाधान की दक्षता के लिए एक अच्छा सहायक हो सकता है। यदि हम बढ़ते क्रम में क्रमबद्ध करते हैं, तो सबसे बड़ा तत्व सूचकांक m-1 पर होगा, और अगला छोटा होगा। इसलिए, शर्त को पूरा करने वाले सबसे बड़े तत्व को ढूंढना आसान है।
एल्गोरिदम
आरंभीकरण maxSum = 0, currMax
चरण 1 -
सरणियों की सरणी की प्रत्येक सरणी को क्रमबद्ध करें (प्रत्येक में तत्व बढ़ते क्रम में होंगे)।
चरण 2 -
currMax = mat[n-1][m-1], अंतिम पंक्ति का अंतिम तत्व। maxSum अपडेट करें, maxSum = currMax।
चरण 3 -
मैट्रिक्स को पंक्तिवार लूप करें, i = n-2 से 0 तक।
चरण 3.1 -
mat[i][] में currMax से छोटे अधिकतम तत्व को सूचकांक j पर ढूंढें।
चरण 3.2 -
यदि j < 0, यानी कोई मान नहीं मिला। Return -1।
चरण 3.3 -
currMax अपडेट करें। currMax = mat[i][j]।
चरण 3.4 -
maxSum अपडेट करें, maxSum = currMax।
चरण 4 -
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