एक पूर्णांक सरणी और मान K दिया गया है। ऐसा उपअनुक्रम ढूंढें जिसका योग अधिकतम हो और जिसमें किन्हीं दो तत्वों के इंडेक्स में कम से कम K का अंतर हो।
उदाहरण: सरणी {50, 70, 40, 50, 90, 70, 60, 40, 70, 50}, K=2 → अधिकतम योग 230।
समाधान दृष्टिकोण (DP)
MS[i] = इंडेक्स i से शुरू होने वाले वैध उपअनुक्रम का अधिकतम योग।
MS[N-1] = arr[N-1]।- i = N-2 से 0 तक पीछे जाएं:
- यदि
i + k + 1 >= N:MS[i] = max(arr[i], MS[i+1])। - अन्यथा:
MS[i] = max(arr[i] + MS[i+k+1], MS[i+1])।
- यदि
MS[0]वापस करें।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
int maxSum(int arr[], int N, int k) {
int MS[N];
MS[N - 1] = arr[N - 1];
for (int i = N - 2; i >= 0; i--) {
if (i + k + 1 >= N)
MS[i] = max(arr[i], MS[i + 1]);
else
MS[i] = max(arr[i] + MS[i + k + 1], MS[i + 1]);
}
return MS[0];
}
int main() {
int N = 10, k = 2;
int arr[] = {50, 70, 40, 50, 90, 70, 60, 40, 70, 50};
cout << maxSum(arr, N, k);
return 0;
}
आउटपुट
230