C++ में दो गैर-अतिव्यापी उपसरणियों का अधिकतम योग

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

• n :=A का आकार

• आकार n के बाएं एल सरणी को परिभाषित करें, आकार एन के बाएं एम सरणी को परिभाषित करें

• आकार n के दाएं एल सरणी को परिभाषित करें, आकार n के दाएं सरणी को परिभाषित करें

• रिट:=0, अस्थायी:=0

• प्रारंभ करने के लिए i :=0, जब i

  • अस्थायी =अस्थायी + ए[i]

• i :=L, j :=0 को इनिशियलाइज़ करने के लिए, जब i

  • leftL[i − 1] :=अधिकतम अस्थायी और x जहां x 0 है जब i − 2 <0 अन्यथा x =leftL[i − 2]

  • अस्थायी =अस्थायी + ए[i]

  • अस्थायी =अस्थायी - ए[जे]

• leftL[n − 1] :=अधिकतम तापमान, और x जहां x 0 है, जब n − 2 <0 अन्यथा x :=leftL[n − 2]

• अस्थायी:=0

• प्रारंभ करने के लिए i :=0, जब i

  • अस्थायी =अस्थायी + ए[i]

• i :=M, j :=0 को इनिशियलाइज़ करने के लिए, जब i

  • अस्थायी =अस्थायी + ए[i]

  • अस्थायी =अस्थायी - ए[जे]

• leftM[n − 1] :=अधिकतम अस्थायी और x जब x :=0 यदि n - 2 <0 अन्यथा x :=leftM[n − 2]

• अस्थायी:=0

• i :=n − 1 को प्रारंभ करने के लिए, जब i> n − 1 − L, i को 1 से घटाएं -

  • अस्थायी =अस्थायी + ए[i]

• i :=n − 1 - L, j :=n − 1 को इनिशियलाइज़ करने के लिए, जब i>=0, i को 1 से घटाएं, j को 1 से घटाएं -

  • राइट एल [i + 1]:=अधिकतम अस्थायी और x जहां x 0 है यदि i + 2> =n अन्यथा x =दायां एल [i + 2]

  • अस्थायी =अस्थायी + ए[i]

  • अस्थायी =अस्थायी - ए[जे]

• दायां एल [0]:=अधिकतम तापमान और दायां एल [1]

• अस्थायी:=0

• i :=n − 1 को प्रारंभ करने के लिए, जब i> n − 1 − M, i को 1 से घटाएं -

  • अस्थायी =अस्थायी + ए[i]

• i :=n − 1 − M, j :=n − 1 को इनिशियलाइज़ करने के लिए, जब i>=0, i को 1 से घटाएं, j को 1 से घटाएं -

  • दायां एम [i + 1]:=अधिकतम अस्थायी और एक्स, जहां एक्स 0 है जब i + 2> =n अन्यथा x:=दायां एम [i + 2]

  • अस्थायी =अस्थायी + ए[i]

  • अस्थायी =अस्थायी - ए[जे]

• दायां एम [0]:=अधिकतम तापमान और दायां एम [1]

• i :=L − 1 को इनिशियलाइज़ करने के लिए, जब i <=n - 1 - M, i को 1 से बढ़ाएँ -

  • रिट :=अधिकतम रिट और लेफ्टएल[i] + राइटएम[i + 1]

• i :=M - 1 को इनिशियलाइज़ करने के लिए, जब i <=n - 1 - L, i को 1 से बढ़ाएँ -

  • रिट :=अधिकतम रिट और लेफ्टएम[i] + राइटएल[i + 1]

• वापसी रिट

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
      int n = A.size();
      vector <int> leftL(n);
      vector <int> leftM(n);
      vector <int> rightL(n);
      vector <int> rightM(n);
      int ret = 0;
      int temp = 0;
      for(int i = 0; i < L; i++){
         temp += A[i];
      }
      for(int i = L, j = 0; i < n; i++, j++){
         leftL[i − 1] = max(temp, i − 2 < 0 ? 0 : leftL[i − 2]);
         temp += A[i];
         temp −= A[j];
      }
      leftL[n − 1] = max(temp, n − 2 < 0 ? 0 : leftL[n − 2]);
      temp = 0;
      for(int i = 0; i < M; i++){
         temp += A[i];
      }
      for(int i = M, j = 0; i < n; i++, j++){
         leftM[i − 1] = max(temp, i − 2 < 0 ? 0 : leftM[i − 2]);
         temp += A[i];
         temp −= A[j];
      }
      leftM[n − 1] = max(temp, n − 2 < 0 ? 0 : leftM[n − 2]);
      //out(leftM);
      temp = 0;
      for(int i = n − 1; i > n − 1 − L; i−−){
         temp += A[i];
      }
      for(int i = n − 1 − L, j = n − 1; i >= 0 ; i−−, j−− ){
         rightL[i + 1] = max(temp, (i + 2 >= n ? 0 : rightL[i + 2]));
         temp += A[i];
         temp −= A[j];
      }
      rightL[0] = max(temp, rightL[1]);
      temp = 0;
      for(int i = n − 1; i > n − 1 − M; i−−){
         temp += A[i];
      }
      for(int i = n − 1 − M, j = n − 1; i >= 0 ; i−−, j−− ){
         rightM[i + 1] = max(temp, (i + 2 >= n ? 0 : rightM[i + 2]));
         temp += A[i];
         temp −= A[j];
      }
      rightM[0] = max(temp, rightM[1]);
      for(int i = L − 1; i <= n − 1 − M; i++){
         ret = max(ret, leftL[i] + rightM[i + 1]);
      }
      for(int i = M − 1; i <= n − 1 − L; i++){
         ret = max(ret, leftM[i] + rightL[i + 1]);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v1 = {0,6,5,2,3,5,1,9,4};
   cout << (ob.maxSumTwoNoOverlap(v1, 1, 2));
}

इनपुट

[0,6,5,2,3,5,1,9,4]
1
2

आउटपुट

20