इस समस्या में, हमें n आकार की एक सरणी arr[] और एक संख्या k दी गई है। हमारा कार्य कम से कम दूर के तत्वों के साथ अधिकतम योग परिणाम खोजने के लिए एक कार्यक्रम बनाना है।
समस्या का विवरण - हमें सबअरे का योग इस तरह निकालने की जरूरत है कि सबएरे के तत्वों को एरे से लिया जाए जिसका इंडेक्स k दूरी पर हो और योग अधिकतम हो।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {2, 3, 7, 9, 2, 8, 3} आउटपुट
15
स्पष्टीकरण
All subsequences that satisfy the given condition,
{2, 9, 3}, Sum = 14
{3, 2}, Sum = 5
{7, 8}, Sum = 15 समाधान दृष्टिकोण
समस्या का एक सरल समाधान सभी संभावित उप-सरणियों को खोजना है जो दी गई स्थिति को संतुष्ट करते हैं। सभी सरणियों का योग ज्ञात करें और सभी का अधिकतम वापस करें।
समस्या का एक अधिक कुशल समाधान एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करके वर्तमान तत्व तक अधिकतम योग को संग्रहीत करने के लिए एक सरणी बनाकर है। वर्तमान तत्व के लिए, हम या तो इसे योग के लिए मान सकते हैं या इसे योग के लिए त्याग सकते हैं, जो भी योग को वर्तमान सूचकांक तक बढ़ाता है।
अगर हम इसे योग के लिए मानते हैं, तो योग [i] =योग [i + k + 1] + arr [i+1] अन्यथा इसे योग के लिए छोड़ दें, योग [i] =योग [i + 1] और अंत में अधिकतम योग लौटाएं जो योग [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