【C++】3つの連続要素を選ばない最大部分列の和を求める方法｜動的計画法で解説

問題概要

この問題では、n個の正の整数からなる配列 arr[] が与えられます。求めるのは、「3つの連続した要素を選ばない」という制約のもとで、選んだ要素の和を最大化することです。

ここでいう「連続する要素」とは、配列内でインデックスが順番どおりに並んでいる要素のことを指します。

arr[0], arr[1], arr[2], …

入出力例

入力

arr[] = {5, 9, 12, 15}

出力

32

説明

和 = 5 + 12 + 15 = 32

この例では、9 を除外することで「3連続」を避け、残りの要素をすべて選んでいます。もし {9, 12, 15} のように3つ連続で選ぶと制約違反となるため、{5, 12, 15} が最適な選択になります。

解法アプローチ

最もシンプルな解法は、各インデックスまでの最大和を記録する補助配列を作成することです。これにより、連続性の制約を確認しながら、先頭から順に最大値を更新していきます。

まず、最初の2つの値は次のように初期化します。

sumVal[0] = arr[0]
sumVal[1] = arr[0] + arr[1]

3番目以降の要素は単純には足せません。arr[i] を加えるかどうかは、直前の3つの要素との関係で判断します。

• arr[i] を採用する場合： 和が増加するなら、arr[i−1] または arr[i−2] のいずれかを除外します。
• arr[i] を採用しない場合： 和は sumVal[i−1] のまま維持します。

これらの条件を漸化式で表すと、次のようになります。

sum[i] = max(sum[i−3] + arr[i−1] + arr[i], sum[i−2] + arr[i], sum[i−1])

• sum[i−3] + arr[i−1] + arr[i]： i−1 と i を連続2つとして選び、それより前は i−3 までの結果を使うパターン
• sum[i−2] + arr[i]： i のみを選び、それより前は i−2 までの結果を使うパターン
• sum[i−1]： arr[i] を選ばないパターン

C++での実装例

上記の解法を実装したプログラムがこちらです。

#include <iostream>
using namespace std;

int findMaxSubSeqSum(int arr[], int n) {
    int maxSumArr[n];
    maxSumArr[0] = arr[0];
    maxSumArr[1] = arr[0] + arr[1];
    maxSumArr[2] = max(maxSumArr[1], max(arr[1] + arr[2], arr[0] + arr[2]));
    for (int i = 3; i < n; i++) {
        int sum1 = maxSumArr[i - 2] + arr[i];
        int sum2 = arr[i] + arr[i - 1] + maxSumArr[i - 3];
        maxSumArr[i] = max(max(maxSumArr[i - 1], sum1), sum2);
    }
    return maxSumArr[n - 1];
}

int main() {
    int arr[] = { 5, 9, 12, 15 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum subsequence sum such that no three are consecutive is "
         << findMaxSubSeqSum(arr, n);
    return 0;
}

出力

The maximum subsequence sum such that no three are consecutive is 32

計算量

• 時間計算量： O(n) — 配列を一度走査するだけで済みます。
• 空間計算量： O(n) — 各インデックスまでの最大和を保持する補助配列が必要です。

まとめ

「3つの連続要素を選ばない最大部分列の和」問題は、動的計画法（DP）を使えば効率的に解くことができます。ポイントは、直近3つの状態を比較する漸化式を立てることです。この考え方は、隣接する要素を同時に選べない「House Robber」系の問題にも応用できる、非常に有用なテクニックです。