C++ प्रोग्राम में ऐरे में दूरी < K पर कोई दो तत्व न आने पर सब-सीक्वेंस के लिए अधिकतम संभव योग

समस्या विवरण

इस समस्या में, हमें आकार n का एक ऐरे arr[] और एक पूर्णांक k दिया गया है। हमारा कार्य ऐसा प्रोग्राम बनाना है जो ऐरे में दूरी < K पर कोई दो तत्व न आने पर सब-सीक्वेंस के लिए अधिकतम संभव योग ढूंढे।

समस्या विवरण - हमें सब-सीक्वेंस का अधिकतम योग ढूंढना है जो उन तत्वों पर विचार करता है जो एक दूसरे से k दूरी पर हैं।

उदाहरण

arr[] = {6, 2, 5, 1, 9, 11, 4} k = 2

आउटपुट

16

व्याख्या

कम से कम k दूरी वाले तत्वों के सभी संभावित सब-सीक्वेंस:
{6, 1, 4}, योग = 11
{2, 9}, योग = 11
{5, 11}, योग = 16
{1, 4}, योग = 5
... अधिकतम योग = 16

हल करने का दृष्टिकोण

समस्या का एक हल डायनामिक प्रोग्रामिंग का उपयोग करना है। हल के लिए, हम ऐरे के वर्तमान तत्व तक अधिकतम संभव योग ढूंढेंगे। और इसे DP[i] में संग्रहीत करेंगे, इसके लिए हम अधिकतम संभव योग ढूंढेंगे। i-वें इंडेक्स के लिए, हमें जांचना होगा कि वर्तमान इंडेक्स मान जोड़ने से सब-सीक्वेंस योग बढ़ता है या नहीं।

if( DP[i - (k+1)] + arr[i] > DP[i - 1] ) -> DP[i] = DP[i - (k+1)] + arr[i] otherwise DP[i] = DP[i-1]

डायनामिक ऐरे का अधिकतम तत्व अधिकतम सबसीक्वेंस योग देता है।

एल्गोरिदम

1. आरंभीकरण - maxSumSubSeq = -1, maxSumDP[n]
2. चरण 1 - maxSumDP[0] = arr[0] आरंभ करें
3. चरण 2 - i -> 1 से n तक लूप
   • चरण 2.1 - यदि i < k -> maxSumDP[i] = max(arr[i], maxSumDP[i-1])
   • चरण 2.2 - अन्यथा, maxSumDP[i] = max(arr[i], maxSumDP[i - (k+1)] + arr[i])
4. चरण 3 - maxSumDP के सभी तत्वों से अधिकतम मान ढूंढें और maxSumSubSeq में संग्रहीत करें
5. चरण 4 - maxSumSubSeq वापस करें

उदाहरण

#include <iostream>
using namespace std;

int retMaxVal(int a, int b) {
    if (a > b) return a;
    return b;
}

int calcMaxSumSubSeq(int arr[], int k, int n) {
    int maxSumDP[n];
    int maxSum = -1;
    maxSumDP[0] = arr[0];
    for (int i = 1; i < n; i++) {
        if (i < k) {
            maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i - 1]);
        } else {
            maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i - (k + 1)] + arr[i]);
        }
    }
    for (int i = 0; i < n; i++)
        maxSum = retMaxVal(maxSumDP[i], maxSum);
    return maxSum;
}

int main() {
    int arr[] = {6, 2, 5, 1, 9, 11, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << "The maximum sum possible for a sub-sequence such that no two elements appear at a distance < " << k << " in the array is " << calcMaxSumSubSeq(arr, k, n);
    return 0;
}

आउटपुट

The maximum sum possible for a sub-sequence such that no two elements appear at a distance < 2 in the array is 16