C++ में M तत्वों को चुनें ताकि सन्निहित पुनरावृत्ति K से अधिक न हो और अधिकतम योग प्राप्त हो

इस समस्या में, हमें एक ऐरे arr[] और दो पूर्णांक M और K दिए गए हैं। हमारा कार्य दिए गए ऐरे के तत्वों का उपयोग करके एक ऐरे बनाना है। नए ऐरे का आकार M होना चाहिए और आकार K से बड़े किसी भी सब-ऐरे के सभी तत्व समान नहीं हो सकते। हमें बने ऐरे द्वारा संभव अधिकतम योग प्रिंट करना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं

इनपुट - arr[] = {1, 2, 4, 5, 7}, M = 5, K = 2

व्याख्या - शर्त को पूरा करने वाला बना ऐरे {7, 7, 5, 7, 7}। यहां, आकार 2 से बड़ा कोई सब-ऐरे सभी समान तत्व नहीं रख सकता।

इस समस्या को हल करने के लिए, हमें अधिकतम मान वाले तत्व का उपयोग करके एक ऐरे बनाना होगा। लेकिन हम अधिकतम तत्व का उपयोग K बार से अधिक नहीं कर सकते, इसलिए K बार के बाद हमें ऐरे के दूसरे अधिकतम तत्व का उपयोग करना होगा। ऐरे में हर K अधिकतम मान के बाद एक दूसरा अधिकतम मान डालें और M लंबाई का ऐरे बनाएं। अंतिम आउटपुट इस ऐरे के सभी तत्वों का योग होगा।

उदाहरण

हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम,

#include <iostream>
using namespace std;

long int arraySum(int arr[], int n, int m, int k) {
    int max1 = arr[0], max2 = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max1) {
            max2 = max1;
            max1 = arr[i];
        } else if (arr[i] > max2)
            max2 = arr[i];
    }
    int max2count = m / (k + 1);
    long int sum = max2count * max2 + (m - max2count) * max1;
    return sum;
}

int main() {
    int arr[] = {1, 3, 6, 7, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 9, k = 2;
    cout << "दिए गए ऐरे से बने ऐरे का अधिकतम योग जैसे कि आकार " << k
         << " से बड़ा कोई सबऐरे समान तत्व नहीं रखेगा: ";
    cout << arraySum(arr, n, m, k);
    return 0;
}

आउटपुट

दिए गए ऐरे से बने ऐरे का अधिकतम योग जैसे कि आकार 2 से बड़ा कोई सबऐरे समान तत्व नहीं रखेगा: 60