सी ++ में अधिकतम दो तत्वों को बदलने के बाद अधिकतम सबरे योग

इस समस्या में, हमें एक सरणी दी जाती है। हमारा काम एक ऐसा प्रोग्राम बनाना है जो C++ में अधिकतम दो तत्वों को उलटने के बाद अधिकतम सबएरे योग प्राप्त करेगा।

समस्या का विवरण - यहां, हमें सबएरे को खोजना होगा जो कि एरे के किन्हीं दो नंबरों के चिन्ह को उलटने पर अधिकतम योग उत्पन्न करेगा।

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

इनपुट - सरणी ={-5, 1, 3, 8, -2, 4, 7}

आउटपुट -30

स्पष्टीकरण - हम अधिकतम योग के साथ सरणी प्राप्त करने के लिए इंडेक्स 0 से 6 तक के तत्वों पर विचार करेंगे और -5 और -2 के मानों को उल्टा करेंगे।

इस समस्या को हल करने के लिए, हम एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। हम आकार 1 से n (सरणी की लंबाई) के सभी उप-सरणी के अधिकतम योग की जांच करेंगे। इसलिए, प्रत्येक उप-सरणी के लिए, हमारे पास तीन मामले हैं -

केस1 - उपसरणी के दो तत्वों को उलटने के बाद उपसरणी का अधिकतम योग।

केस2 - उपसरणी के एक तत्व को उलटने के बाद उपसरणी का अधिकतम योग।

केस3 - उपसरणी के शून्य तत्वों को उलटने के बाद उपसरणी का अधिकतम योग।

इसलिए, हमारे पास प्रत्येक पुनरावृत्ति के लिए, हम अधिकतम सरणी का अधिकतम योग, और वर्तमान तत्व पाएंगे और अधिकतम को प्रारंभ करेंगे।

हम अधिकतम राशि को मैक्ससम नामक 2डी सरणी में संग्रहित करेंगे। और अंतिम अधिकतम राशि 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