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

इस समस्या में, हमें एक ऐरे एरर [] दिया जाता है। हमारा कार्य अधिकतम योग ज्ञात करने के लिए एक प्रोग्राम बनाना है जैसे कि C++ में कोई भी दो तत्व आसन्न न हों।

समस्या का विवरण

हमें सरणी से अनुक्रम का अधिकतम योग खोजने की आवश्यकता है जैसे कि योग अनुक्रम से कोई भी 2 संख्याएं सरणी में आसन्न नहीं हैं।

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

इनपुट

arr[] = {5, 1, 3, 7, 9, 2, 5}

आउटपुट

22

स्पष्टीकरण

Taking sum sequence from index 0 with alternate elements : 5 + 3 + 9 + 5 = 22
Taking sum sequence from index 1 with alternate elements : 1 + 7 + 2 = 10

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

पिछले सेट में, हमने समस्या को हल करने के लिए एक दृष्टिकोण देखा है। यहां, हम समस्या को हल करने के लिए गतिशील प्रोग्रामिंग दृष्टिकोण के बारे में जानेंगे।

गतिशील दृष्टिकोण का उपयोग करके समस्या को हल करने के लिए, हमें एक DP[] सरणी बनाने की आवश्यकता है जो उस अधिकतम राशि को वर्तमान सूचकांक तक संग्रहीत करती है। और फिर इस गतिशील सरणी का उपयोग करके योग अनुक्रमणिका खोजें।

वर्तमान DP अधिकतम dp[i+2]+ arr[i] और dp[i+1] की अधिकतम है।

उदाहरण

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

#include <iostream>
using namespace std;
int DP[100];
bool currState[100];
int maxVal(int a, int b){
   if(a > b)
      return a;
      return b;
   }
int calcMaxSumWOAdj(int arr[], int i, int n){
   if (i >= n)
      return 0;
   if (currState[i])
      return DP[i];
   currState[i] = 1;
   DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
   return DP[i];
}
int main(){
   int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
   int n = sizeof(arr) / sizeof(int);
   cout<<"The maximum sum such that no two elements are adjacent is "<<calcMaxSumWOAdj(arr, 0, n);
   return 0;
}

आउटपुट

The maximum sum such that no two elements are adjacent is 22