इस समस्या में, हमें एक सर्कुलर ऐरे cirArr[] दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में सर्कुलर ऐरे में अधिकतम योग ढूंढे जहाँ कोई दो आसन्न तत्व न हों।
समस्या विवरण
सर्कुलर ऐरे के लिए, हमें ऐरे के तत्वों का अधिकतम योग ढूंढना है जहाँ आसन्न तत्वों को नहीं लिया जा सकता, यानी हमें वैकल्पिक तत्व लेने हैं।
सर्कुलर ऐरे एक विशेष प्रकार का ऐरे है जिसमें ऐरे का अंतिम तत्व पहले तत्व से जुड़ा होता है।

आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
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