C++ में n सरणियों से बढ़ते क्रम के तत्वों का अधिकतम योग

N सरणियाँ (प्रत्येक आकार M) दी गई हैं। प्रत्येक सरणी से एक तत्व चुनें ताकि चुने गए तत्व सख्ती से बढ़ते क्रम में हों और उनका योग अधिकतम हो।

रणनीति: प्रत्येक सरणी को सॉर्ट करें। अंतिम सरणी से सबसे बड़ा तत्व लें, फिर उससे छोटा तत्व पिछली सरणी से लें, आदि।

उदाहरण: 3 सरणियों के लिए अधिकतम योग 18।

C++ कार्यान्वयन

#include <bits/stdc++.h>
#define M 4
using namespace std;

int maximumSum(int a[][M], int n) {
    for (int i = 0; i < n; i++) sort(a[i], a[i] + M);
    int sum = a[n - 1][M - 1];
    int prev = a[n - 1][M - 1];
    for (int i = n - 2; i >= 0; i--) {
        for (int j = M - 1; j >= 0; j--) {
            if (a[i][j] < prev) {
                prev = a[i][j];
                sum += prev;
                break;
            }
        }
        if (j == -1) return 0;
    }
    return sum;
}

int main() {
    int arr[][M] = {{1, 7, 3, 4}, {4, 2, 5, 1}, {9, 5, 1, 8}};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maximumSum(arr, n);
    return 0;
}

आउटपुट

18