C++で最長乱流部分配列を求める方法【動的計画法による解説】

配列 A の部分配列 A[i], A[i+1], ..., A[j] が「乱流（turbulent）」であるとは、次のいずれかの条件を満たすことを意味します。

• i ≤ k < j に対して、k が奇数のときは A[k] > A[k+1]、k が偶数のときは A[k] < A[k+1]

• または、i ≤ k < j に対して、k が偶数のときは A[k] > A[k+1]、k が奇数のときは A[k] < A[k+1]

つまり、隣接する要素同士の大小関係が、部分配列全体にわたって交互に入れ替わっている状態が「乱流」です。本記事では、配列 A から最大サイズの乱流部分配列の長さを求める問題を、C++と動的計画法で解いていきます。

例えば、入力が [9,4,2,10,7,8,8,1,9] の場合、答えは 5 になります。これは A[1] > A[2] < A[3] > A[4] < A[5] という大小関係が成り立ち、これより長い乱流部分配列が存在しないためです。

解き方：動的計画法

この問題は動的計画法（DP）を用いることで、時間計算量 O(n)・空間計算量 O(1) で効率的に解けます。手順は以下の通りです。

• n := 配列 A のサイズとする

• prevBig := 1、prevSmall := 1、currBig := 1、currSmall := 1、ret := 1 で初期化する

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

  • A[i] > A[i − 1] のとき、currBig := 1 + prevSmall と更新する

  • A[i] < A[i − 1] のとき、currSmall := 1 + prevBig と更新する

  • ret := ret、currBig、currSmall のうちの最大値に更新する

  • prevSmall := currSmall、prevBig := currBig、currSmall := 1、currBig := 1 に更新する

• ret を返す

ここで currBig は「直前の比較が上昇（A[i−1] < A[i]）」で終わる乱流部分配列の最長の長さ、currSmall は「直前の比較が下降（A[i−1] > A[i]）」で終わる乱流部分配列の最長の長さをそれぞれ表します。隣接する要素が等しい場合など、大小関係が交互に反転しなくなった時点で値は 1 にリセットされる仕組みです。

それでは、理解を深めるために実際の実装を見てみましょう。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxTurbulenceSize(vector<int>& A) {
      int n = A.size();
      int prevBig = 1;
      int prevSmall = 1;
      int currBig = 1;
      int currSmall = 1;
      int ret = 1;
      for(int i = 1; i < n; i++){
         if(A[i] > A[i - 1]){
            currBig = 1 + prevSmall;
         }
         if(A[i] < A[i - 1]){
            currSmall = 1 + prevBig;
         }
         ret = max({ret, currBig, currSmall});
         prevSmall = currSmall;
         prevBig = currBig;
         currSmall = 1;
         currBig = 1;
      }
      return ret;
   }  
};
main(){
   vector<int> v1 = {9,4,2,10,7,8,8,1,9};
   Solution ob;
   cout << (ob.maxTurbulenceSize(v1));
}

入力

[9,4,2,10,7,8,8,1,9]

出力

5