C++ में दूरी < K वाले तत्वों के बिना अधिकतम योग उपअनुक्रम

सरणी और मान K दिया गया है। ऐसा उपअनुक्रम ढूंढें जिसका योग अधिकतम हो और किन्हीं दो चयनित तत्वों के इंडेक्स में अंतर K से कम न हो।

उदाहरण: {6, 7, 1, 3, 8, 2, 4}, K=2 → अधिकतम योग 15।

समाधान दृष्टिकोण (DP)

• dp[i] = इंडेक्स i तक वैध उपअनुक्रम का अधिकतम योग।
• आधार मामले: n=0,1,2 संभालें।
• i = 1 से k तक: dp[i] = max(arr[i], dp[i-1])।
• i = k+1 से n-1 तक: dp[i] = max(arr[i], dp[i-(k+1)] + arr[i])।
• dp सरणी में अधिकतम वापस करें।

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

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

int maxSum(int* arr, int k, int n) {
    if (n == 0) return 0;
    if (n == 1) return arr[0];
    if (n == 2) return max(arr[0], arr[1]);
    int dp[n];
    dp[0] = arr[0];
    for (int i = 1; i <= k; i++) dp[i] = max(arr[i], dp[i - 1]);
    for (int i = k + 1; i < n; i++) dp[i] = max(arr[i], dp[i - (k + 1)] + arr[i]);
    return *max_element(dp, dp + n);
}

int main() {
    int arr[] = {6, 7, 1, 3, 8, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << maxSum(arr, k, n);
    return 0;
}

आउटपुट

15