समस्या विवरण
इस समस्या में, हमें आकार n का एक ऐरे arr[] और एक संख्या k दी गई है। हमारा कार्य कम से कम k दूर तत्वों के साथ अधिकतम योग सबसीक्वेंस ढूंढने का प्रोग्राम बनाना है।
समस्या विवरण - हमें सबऐरे का योग ढूंढना है जैसे कि सबऐरे के तत्व ऐरे से लिए गए हैं जिनका इंडेक्स k दूरी पर है और योग अधिकतम है।
उदाहरण
arr[] = {2, 3, 7, 9, 2, 8, 3}
आउटपुट
15
व्याख्या
दिए गए शर्त को पूरा करने वाले सभी सबसीक्वेंस:
{2, 9, 3}, योग = 14
{3, 2}, योग = 5
{7, 8}, योग = 15
हल करने का दृष्टिकोण
समस्या का एक सरल हल दी गई शर्त को पूरा करने वाले सभी संभावित सबऐरे ढूंढना है। सभी ऐरे का योग ढूंढें और उनमें से अधिकतम वापस करें।
समस्या का एक अधिक कुशल हल डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करके एक ऐरे बनाना है जो वर्तमान तत्व तक अधिकतम योग संग्रहीत करता है। वर्तमान तत्व के लिए, हम या तो इसे योग के लिए विचार कर सकते हैं या इसे योग के लिए त्याग सकते हैं, जो भी वर्तमान इंडेक्स तक योग को बढ़ाता है।
यदि हम इसे योग के लिए विचार करते हैं, sum[i] = sum[i + k + 1] + arr[i+1] अन्यथा इसे त्याग दें, sum[i] = sum[i+1] और अंत में अधिकतम योग वापस करें जो sum[0] पर है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int calcMaxSubSeqSum(int arr[], int N, int k) {
int maxSumDP[N];
maxSumDP[N - 1] = arr[N - 1];
for (int i = N - 2; i >= 0; i--) {
if (i + k + 1 >= N)
maxSumDP[i] = max(arr[i], maxSumDP[i + 1]);
else
maxSumDP[i] = max(arr[i] + maxSumDP[i + k + 1], maxSumDP[i + 1]);
}
return maxSumDP[0];
}
int main() {
int N = 10, k = 2;
int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
cout << "The maximum sum subsequence with at-least k distant elements is " << calcMaxSubSeqSum(arr, N, k);
return 0;
}
आउटपुट
The maximum sum subsequence with at-least k distant elements is 230
