C++での最大合計循環サブ配列

Aで表される整数の循環配列Cがあるとすると、Cの空でないサブ配列の可能な最大合計を見つける必要があります。また、サブ配列には、固定バッファーAの各要素を最大で1回だけ含めることができます。配列が[1、-2,3、-2]のような場合、出力は3になります。これは、subarray[3]の合計が最大3であるためです。

これを解決するには、次の手順に従います-

• n：=vのサイズ

• すべてサイズnの配列leftSum、leftSumMax、rightSum、rightSumMaxを作成します

• leftSum [0]：=v [0]、leftSumMax [0]：=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最大0およびv[n-1]

• n-2から0までの範囲のiの場合

  • rightSum [i]：=rightSum [i + 1] + v [i]

  • rightSumMax [i]：=rightSum [i+1]とrightSumMax[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]

• curr：=v [0]、kadane：=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]

出力

3