C++で循環配列の最大部分配列和を求めるアルゴリズム

問題概要

整数からなる循環配列 C(固定バッファ A で表現)が与えられます。このとき、C の空でない部分配列の合計として考えられる最大値を求めてください。ただし、部分配列に含められるのはバッファ A の各要素につき最大1回までです。例えば、配列が [1, -2, 3, -2] の場合、出力は 3 になります。これは部分配列 [3] の合計が 3 であり、これが最大であるためです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• n := v のサイズとする

• サイズ n の配列 leftSum、leftSumMax、rightSum、rightSumMax を作成する

• leftSum[0] := v[0]、leftSumMax[0] := max(0, v[0]) とする

• i を 1 から n − 1 まで繰り返す

  • 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(0, v[n − 1]) とする

• i を n − 2 から 0 まで降順で繰り返す

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

  • rightSumMax[i] := max(rightSumMax[i + 1], rightSum[i])

• leftAns := leftSum[0] + rightSumMax[1]

• i を 1 から n − 2 まで繰り返す

  • leftAns := max(leftAns, leftSum[i] + rightSumMax[i + 1])

• rightAns := rightSum[n − 1] + leftSumMax[n − 2]

• i を n − 2 から 1 まで降順で繰り返す

  • rightAns := max(rightAns, rightSum[i] + leftSumMax[i − 1])

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

• i を 1 から n − 1 まで繰り返す

  • curr := max(v[i], curr + v[i])

  • kadane := max(curr, kadane)

• max(leftAns, rightAns, kadane) を返す

アルゴリズムのポイント

循環配列における最大部分配列和は、大きく分けて2つのケースを考える必要があります。1つ目は配列の範囲内で完結する通常の部分配列であり、これは Kadane(カダネ)のアルゴリズムで効率よく求められます。2つ目は配列の末尾と先頭をつなぐ「折り返し」を含む部分配列であり、こちらは左側からの累積和(leftSum)と右側からの累積和(rightSum)を組み合わせることで求められます。最終的な答えは、これら2つのケースの結果のうち大きい方となります。計算量は時間・空間ともに O(n) です。

それでは、以下の実装例を見て理解を深めましょう。

実装例

#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