इस समस्या में, हमें एक सरणी arr[] दी गई है। हमारा कार्य C++ में अधिकतम योग ढूंढने के लिए एक प्रोग्राम बनाना है जैसे कि कोई दो तत्व आसन्न न हों।
समस्या विवरण
हमें सरणी से अनुक्रम का अधिकतम योग ढूंढना होगा जैसे कि योग अनुक्रम से कोई 2 संख्याएं सरणी में आसन्न न हों।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {5, 1, 3, 7, 9, 2, 5}
आउटपुट
22
व्याख्या
इंडेक्स 0 से वैकल्पिक तत्वों के साथ योग अनुक्रम लेना: 5 + 3 + 9 + 5 = 22 इंडेक्स 1 से वैकल्पिक तत्वों के साथ योग अनुक्रम लेना: 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<<"अधिकतम योग जैसे कि कोई दो तत्व आसन्न न हों "<<calcMaxSumWOAdj(arr, 0, n); return 0; }
आउटपुट
अधिकतम योग जैसे कि कोई दो तत्व आसन्न न हों 22
