उप-अनुक्रम के लिए अधिकतम संभव योग जैसे कि कोई भी दो तत्व दूरी पर दिखाई नहीं देते हैं <K C++ प्रोग्राम में सरणी में

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

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

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

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

आउटपुट

स्पष्टीकरण

All possible sub−sequences of elements that differ by k or more.
{6, 1, 4}, sum = 11
{2, 9}, sum = 11
{5, 11}, sum = 16
{1, 4}, sum = 5
...
maxSum = 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]

डायनेमिक सरणी का अधिकतम तत्व अधिकतम अनुगमन देता है।

एल्गोरिदम

आरंभ करें -

maxSumSubSeq = −1, maxSumDP[n]

चरण 1 -

Initialize maxSumDP[0] = arr[0]

चरण 2 -

Loop for i −> 1 to n.

चरण 2.1 -

if i < k −> maxSumDP[i] = maximum of arr[i] or
maxSumDP[i− 1].

चरण 2.2 -

else, maxSumDP[i] = maximum of arr[i] or maxSumDP[i − (k + 1)] + arr[i].

चरण 3 -

Find the maximum value of all elements from maxSumDP and store
it to maxSumSubSeq.

चरण 4 -

Return 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

है