C++で最大和の交互部分列を求めるアルゴリズムと実装方法

はじめに

本記事では、C++を用いて「最大和の交互部分列（Alternating Subsequence）」を求めるプログラムについて解説します。

ここで扱う問題は、整数型の配列が与えられたとき、その中から「減少→増加→減少→…」というように増減が交互に入れ替わる部分列を抜き出し、その要素の合計値が最大となるものを見つけるというものです。

アルゴリズムの考え方

この問題は動的計画法（DP）を用いて解くことができます。具体的には、以下の2つの配列を用意します。

• dec[i]: i番目の要素で終わる交互部分列のうち、「直前の操作が減少」である場合の最大和
• inc[i]: i番目の要素で終わる交互部分列のうち、「直前の操作が増加」である場合の最大和

各インデックスiについて、それより前のすべてのインデックスjを走査し、arr[j] > arr[i] のときは減少遷移として dec[i] を更新し、arr[j] < arr[i] のときは増加遷移として inc[i] を更新していきます。最終的に dec 配列と inc 配列全体の中で最大の値が答えとなります。

実装例（C++）

#include<bits/stdc++.h>
using namespace std;
// 最大和の交互部分列を返す関数
int maxAlternateSum(int arr[], int n) {
   if (n == 1) return arr[0];
   int dec[n];
   memset(dec, 0, sizeof(dec));
   int inc[n];
   memset(inc, 0, sizeof(inc));
   dec[0] = inc[0] = arr[0];
   int flag = 0;
   for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
         if (arr[j] > arr[i]) { dec[i] = max(dec[i], inc[j] + arr[i]); flag = 1; }
         else if (arr[j] < arr[i] && flag == 1) inc[i] = max(inc[i], dec[j] + arr[i]);
    }
  }
   int result = INT_MIN;
   for (int i = 0; i < n; i++) {
      if (result < inc[i])
      result = inc[i];
      if (result < dec[i]) result = dec[i];
  }
   return result;
}
int main() {
   int arr[] = {8, 2, 3, 5, 7, 9, 10};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Maximum sum = " << maxAlternateSum(arr , n ) << endl;
   return 0;
}

実行結果

Maximum sum = 25

コードの解説

上記のサンプルでは、配列 {8, 2, 3, 5, 7, 9, 10} が与えられています。この場合、例えば「8 → 2 → 10」という交互部分列を選ぶと、8 + 2 + 10 = 20 となります。しかし、より大きな和を得るには「8 → 2 → 3 → 2 …」のような組み合わせではなく、条件を満たす範囲で最大の要素を選ぶ必要があります。結果として得られる最大和は 25 です。

計算量について

この実装は二重ループを使用しているため、時間計算量は O(n²)、補助配列分の空間計算量は O(n) となります。配列サイズが大きい場合は、O(n) で解く最適化手法（各要素を加算・減算する貪欲法ベースのアプローチなど）も検討するとよいでしょう。

まとめ

C++における最大和交互部分列の問題は、動的計画法を使うことで効率的に解くことができます。「増加」と「減少」の状態を2つの配列で管理するというシンプルな発想がポイントです。ぜひ自身のコードにも応用してみてください。