अधिकतम योग जैसे कि कोई भी दो तत्व आसन्न नहीं हैं C++ प्रोग्राम में वैकल्पिक विधि

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

समस्या का विवरण - हमें उपसरणी का योग ज्ञात करने की आवश्यकता है जिसमें सरणी के तत्व हैं लेकिन सरणी के दो आसन्न तत्वों को ध्यान में नहीं रखा जा सकता है।

उदाहरण

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

इनपुट

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

आउटपुट

स्पष्टीकरण -

Subarray sum are :
{5, 1, 6}, sum = 5 + 1 + 6 = 12
{2, 9}, sum = 2 + 9 = 11

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

यहां, हमारे पास उस समस्या का एक वैकल्पिक समाधान होगा जो गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग कर रही है। इस दृष्टिकोण में, हम दी गई शर्त को पूरा करने वाले और अधिकतम प्रिंट करने वाले परिणाम पाएंगे। हम एक सरणी maxSumDP [n] बनाएंगे जो बनाए गए बाद के अधिकतम उप को संग्रहीत करता है। तत्व maxSumDP[i] इंडेक्स i से n-1 तक तत्वों को लेकर बनाए गए बाद के अधिकतम योग को संग्रहीत करता है। इसके लिए हम या तो सरणी के वर्तमान तत्व पर विचार कर सकते हैं arr[i] i.e.maxSumDP[i] =arr[i] + मैक्ससमडीपी [i + 2]। या सरणी के वर्तमान तत्व पर विचार न करें arr[i] यानी maxSumDP[i] =maxSumDP[i+2]।

एल्गोरिदम

आरंभ करें -

maxSumDP[]

चरण 2 -

initialize the values of maxSumDP[n−1] and maxSumDP[n−2].
maxSumDP[n−1] = arr[n−1] and maxSumDP[n−2] = max(arr[n−1], arr[n−2]).

चरण 2 -

loop for i −> n−2 to 0

चरण 1.2 -

initialize the value of maxSumDP[i],
maxSumDP[i] = maximum of (arr[i] + maxSumDP[i + 2],
maxSumDP[i + 1])

चरण 3 -

Return maxSumDP[0] which is the maximum sum sequence sum.

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
   if(a > b)
   return a;
   return b;
}
int calcMaxSum(int arr[], int n){
   int maxSumDP[n];
   maxSumDP[n−1] = arr[n−1];
   maxSumDP[n−2] = max(arr[n−1], arr[n−2]);
   for (int i = n − 2; i >= 0; i−−) {
      maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i + 2],
      maxSumDP[i + 1]);
   }
   return maxSumDP[0];
}
int main() {
   int arr[] = { 5, 2 , 1, 9, 6 };
   int n = sizeof(arr) / sizeof(int);
   cout<<"The maximum subsequence sum in such a way that no two consecutive elements of the array is "<<calcMaxSum(arr, n);
   return 0;
}

आउटपुट

The maximum subsequence sum in such a way that no two consecutive
elements of the array is 14