C++의 최대 합 원형 부분배열

<시간/>

A로 표시되는 정수의 원형 배열 C가 있다고 가정하고 C의 비어 있지 않은 하위 배열의 가능한 최대 합을 찾아야 합니다. 또한 하위 배열은 고정 버퍼 A의 각 요소를 최대 한 번만 포함할 수 있습니다. 배열이 [1,-2,3,-2]와 같으면 출력은 3이 됩니다. 이는 하위 배열[3]의 최대 합이 3이기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=v의 크기
크기가 n인 모든 배열 leftSum, leftSumMax, rightSum, rightSumMax 생성
leftSum[0] :=v[0], leftSumMax[0] :=최대값 0 및 v[0]
범위 1에서 n – 1까지의 i에 대해
- leftSum[i] :=leftSum[i - 1] + v[i]
- leftSumMax[i] :=leftSum[i] 및 leftSumMax[i - 1]
  의 최대값
rightSum[n - 1] :=v[n - 1], leftSumMax[n - 1] :=최대값 0 및 v[n - 1]
범위 n - 2에서 0까지의 i에 대해
- rightSum[i] :=rightSum [i + 1] + v[i]
- rightSumMax[i] :=rightSum[i + 1] 및 rightSum Max[i]
  의 최대값
leftAns :=leftSum[0] + rightSumMax[1]
범위 1에서 n – 2의 i에 대해
- leftAns :=leftAns의 최대값, leftSum[i] + rightSumMax[i + 1]
rightAns :=rightSum[n - 1] + leftSumMax[n - 2]
범위 n - 2에서 1까지의 i에 대해
- rightAns :=rightAns의 최대값, rightSum[i] + leftSumMax[i - 1]
커 :=v[0], 카다네 :=v[0]
범위 1에서 n – 1까지의 i에 대해
- curr :=v[1]의 최대값, curr + v[i]
- kadane :=curr 및 kadane의 최대값
leftAns, rightAns 및 kadane의 최대값을 반환합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]