C++ में अधिकतम योग सर्कुलर सबरे

मान लीजिए कि हमारे पास ए द्वारा दर्शाए गए पूर्णांकों की एक गोलाकार सरणी सी है, हमें सी के एक गैर-रिक्त उपसरणी का अधिकतम संभव योग खोजना होगा। साथ ही, एक सबरे में केवल एक बार में निश्चित बफर ए के प्रत्येक तत्व को शामिल किया जा सकता है। यदि सरणी [1,-2,3,-2] की तरह है, तो आउटपुट 3 होगा। ऐसा इसलिए है क्योंकि सबरे [3] में अधिकतम योग 3 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n:=वी का आकार

• सरणियाँ बनाएँ लेफ्टसम, लेफ्टसममैक्स, राइटसम, राइटसममैक्स सभी आकार n

• लेफ्टसम [0]:=वी [0], लेफ्टसममैक्स [0]:=अधिकतम 0 और वी [0]

• मैं के लिए 1 से n - 1 की सीमा में

  • लेफ्टसम [i] :=लेफ्टसम [i - 1] + v[i]

  • लेफ्टसममैक्स [i]:=अधिकतम लेफ्टसम [i] और लेफ्टसममैक्स [i - 1]

• राइटसम [एन -1]:=वी [एन -1], लेफ्टसममैक्स [एन -1]:=अधिकतम 0 और वी [एन -1]

• मेरे लिए n - 2 से 0 तक की श्रेणी में है

  • राइटसम [i]:=राइटसम [i + 1] + v[i]

  • राइटसममैक्स [i]:=अधिकतम राइटसम [i + 1] और राइटसम मैक्स [i]

• लेफ्टएन्स:=लेफ्टसम [0] + राइटसममैक्स [1]

• मैं के लिए 1 से n - 2 की सीमा में

  • बायांएं:=अधिकतम बाएं उत्तर, बाएं योग [i] + दायां सममैक्स [i + 1]

• दायां उत्तर:=दायां योग [एन -1] + बाएं सममैक्स [एन - 2]

• मेरे लिए n - 2 से लेकर 1 तक की श्रेणी में है

  • दायां उत्तर:=अधिकतम दायां उत्तर, दायां योग [i] + बायां सममैक्स [i - 1]

• curr:=v[0], kadane:=v[0]

• मैं के लिए 1 से n - 1 की सीमा में

  • curr :=अधिकतम v[1], curr + v[i]

  • कडाने :=करी और कडाने की अधिकतम

• बाएँ उत्तर, दाएँ उत्तर और कडाने का अधिकतम लौटाएँ

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxSubarraySumCircular(vector<int>& v) {
      int n = v.size();
      vector <int> leftSum(n),leftSumMax(n),rightSum(n), rightSumMax(n);
      leftSum[0] = v[0];
      leftSumMax[0] = max((int)0,v[0]);
      for(int i =1;i<n;i++){
         leftSum[i] = leftSum[i-1] + v[i];
         leftSumMax[i] = max(leftSum[i],leftSumMax[i-1]);
      }
      rightSum[n-1] = v[n-1];
      rightSumMax[n-1] = max((int)0,v[n-1]);
      for(int i =n-2;i>=0;i--){
         rightSum[i] = rightSum[i+1]+v[i];
         rightSumMax[i] = max(rightSumMax[i+1],rightSum[i]);
      }
      int leftAns=leftSum[0]+rightSumMax[1];
      for(int i =1;i<n-1;i++){
         leftAns = max(leftAns,leftSum[i]+rightSumMax[i+1]);
      }
      int rightAns = rightSum[n-1]+leftSumMax[n-2];
      for(int i =n-2;i>=1;i--){
         rightAns = max(rightAns,rightSum[i]+leftSumMax[i-1]);
      }
      int curr=v[0];
      int kadane = v[0];
      for(int i =1;i<n;i++){
         curr = max(v[i],curr+v[i]);
         kadane = max(curr,kadane);
      }
      return max(leftAns,max(rightAns,kadane));
   }
};
main(){
   vector<int> v = {1,-2,3,-2};
   Solution ob;
   cout << (ob.maxSubarraySumCircular(v));
}

इनपुट

[1,-2,3,-2]

आउटपुट

3