इस समस्या में, हमें एक सरणी दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में अधिकतम दो तत्वों को उलटने के बाद अधिकतम सबएरे सम ढूंढेगा।
समस्या विवरण - यहां, हमें वह सबएरे ढूंढना है जो सरणी के किन्हीं दो संख्याओं के चिह्न को उलटने पर अधिकतम सम उत्पन्न करेगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - सरणी = {-5, 1, 3, 8, -2, 4, 7}
आउटपुट - 30
व्याख्या - हम इंडेक्स 0 से 6 तक के तत्वों पर विचार करेंगे और -5 और -2 के मानों को उलटकर अधिकतम सम वाली सरणी प्राप्त करेंगे।
इस समस्या को हल करने के लिए, हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। हम आकार 1 से n (सरणी की लंबाई) तक के सभी सबएरे के अधिकतम सम की जांच करेंगे। इसलिए, प्रत्येक सबएरे के लिए हमारे तीन मामले हैं -
केस 1 - सबएरे के दो तत्वों को उलटने के बाद सबएरे का अधिकतम सम।
केस 2 - सबएरे के एक तत्व को उलटने के बाद सबएरे का अधिकतम सम।
केस 3 - सबएरे के शून्य तत्वों को उलटने के बाद सबएरे का अधिकतम सम।
इसलिए, हमारे पास प्रत्येक पुनरावृत्ति के लिए, हम सरणी के अधिकतम सम और वर्तमान तत्व का अधिकतम ढूंढेंगे और अधिकतम को उससे प्रारंभ करेंगे।
हम अधिकतम सम को maxSum नामक एक 2D सरणी में संग्रहीत करेंगे। और अंतिम maxSum 2D सरणी के सभी तत्वों का अधिकतम होगा।
उदाहरण
हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम,
#include <bits/stdc++.h> using namespace std; int findMaxSubarraySum(int a[], int n) { int maxSubarraySum = 0; int* arr = new int[n + 1]; for (int i = 1; i <= n; i++) arr[i] = a[i - 1]; int** maxSum = new int*[n + 1]; for (int i = 0; i <= n; i++) maxSum[i] = new int[3]; for (int i = 1; i <= n; ++i) { maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]); maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i]; if (i >= 2) maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]); if (i >= 2) maxSum[i][2] = maxSum[i - 1][1] - arr[i]; if (i >= 3) maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]); maxSubarraySum = max(maxSubarraySum, maxSum[i][0]); maxSubarraySum = max(maxSubarraySum, maxSum[i][1]); maxSubarraySum = max(maxSubarraySum, maxSum[i][2]); } return maxSubarraySum; } int main(){ int arr[] = {-5, 1, 3, 8, -2, 4, 7}; int n = sizeof(arr) / sizeof(arr[0]); cout<<"Maximum subarray sum after inverting at most two elements is "<<findMaxSubarraySum(arr, n); return 0; }आउटपुट
Maximum subarray sum after inverting at most two elements is 30
