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

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

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

वृत्ताकार सरणी के लिए, हमें सरणी के तत्वों का अधिकतम योग ज्ञात करना होगा जैसे कि आसन्न तत्वों को नहीं लिया जा सकता है यानी हमें वैकल्पिक तत्वों को लेने की आवश्यकता है।

गोलाकार सरणी एक विशेष प्रकार का सरणी है जिसमें सरणी का अंतिम तत्व पहले तत्व से जुड़ा होता है।

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

इनपुट

cirArr[] = {4, 1, 5, 3, 2}

आउटपुट

9

स्पष्टीकरण

सर्कुलर परवर्ती का अधिकतम योग [4, 5, 2] है। योग =9

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

समस्या का समाधान अधिकतम योग खोजने के लिए एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग कर रहा है। वृत्ताकार सरणी को दो सरणियों के रूप में मानकर योग निकाला जा सकता है, एक सूचकांक 0 से N-2 तक और दूसरा सूचकांक 1 से n-1 तक। यह दो सरणियाँ बनाएगा और इन सरणी से अधिकतम योग परिणाम होगा।

उदाहरण

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

#include <iostream>
using namespace std;
int calcMaxVal(int a, int b){
   if(a > b)
      return a;
   return b;
}
int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
   int DP[n];
   int maxSum = 0;
   for (int i = start; i < (end + 1); i++) {
      DP[i] = cirArr[i];
      if (maxSum < cirArr[i])
         maxSum = cirArr[i];
   }
   for (int i = (start + 2); i < (end + 1); i++) {
      for (int j = 0; j < i - 1; j++) {
         if (DP[i] < DP[j] + cirArr[i]) {
            DP[i] = DP[j] + cirArr[i];
            if (maxSum < DP[i])
               maxSum = DP[i];
         }
      }
   }
   return maxSum;
}
int findMaxSum(int cirArr[], int n){
   int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n-2), n);
   int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n-1), n);
   int maxSum = calcMaxVal(maxSumArray1, maxSumArray2);
   return maxSum;
}
int main(){
   int cirArr[] = {4, 1, 5, 3, 2};
   int n = sizeof(cirArr)/sizeof(cirArr[0]);
   cout<<"The maximum sum in circular array such that no two elements are adjacent is "<<findMaxSum(cirArr, n);
   return 0;
}

आउटपुट

The maximum sum in circular array such that no two elements are adjacent is 9