隣接する2つの要素を選ばない最大部分列和を求めるC++プログラム|動的計画法による別解

問題概要

この問題では、正の整数からなるサイズ n の配列 arr[] が与えられます。求めるのは、配列内で隣接する2つの要素を同時に選択しないという制約のもとで、部分列の合計が最大になる組み合わせを見つけることです。

入出力例

入力:

arr[] = {5, 2, 1, 9, 6}

出力: 14

説明: 条件を満たす部分列には以下のようなものがあります。

{5, 1, 6} → 合計 = 5 + 1 + 6 = 12
{2, 9} → 合計 = 2 + 9 = 11
{5, 9} → 合計 = 5 + 9 = 14(最大)

解法アプローチ:動的計画法(DP)

ここでは、動的計画法を用いた効率的な別解を紹介します。この手法では、条件を満たす部分列の最大和を配列の後ろから順に求めながら、最終的な答えを導き出します。

まず、長さ n の配列 maxSumDP[] を用意します。maxSumDP[i] には「インデックス i から n-1 までの要素で構成できる部分列の最大和」を格納します。

maxSumDP[i] の値は、次の2つの選択のうち大きい方となります。

• arr[i] を選ぶ場合: 隣接する要素は使えないため、maxSumDP[i] = arr[i] + maxSumDP[i + 2]
• arr[i] を選ばない場合: maxSumDP[i] = maxSumDP[i + 1]

アルゴリズムの手順

ステップ1: DPテーブル maxSumDP[] を宣言します。

ステップ2: ベースケースとして、配列末尾の2つの値を初期化します。

maxSumDP[n-1] = arr[n-1]
maxSumDP[n-2] = max(arr[n-1], arr[n-2])

ステップ3: i を n-3 から 0 まで逆順にループし、次の漸化式で値を更新します。

maxSumDP[i] = max(arr[i] + maxSumDP[i + 2], maxSumDP[i + 1])

※ 注意点として、ループの開始点は必ず n-3 にしてください。n-2 から始めると maxSumDP[i + 2] が配列の範囲外を参照し、未定義動作を引き起こす可能性があります。

ステップ4: 求める最大部分列和である maxSumDP[0] を返します。

C++実装例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int calcMaxSum(const vector<int>& arr, int n) {
    vector<int> maxSumDP(n);

    // ベースケース
    maxSumDP[n - 1] = arr[n - 1];
    maxSumDP[n - 2] = max(arr[n - 1], arr[n - 2]);

    // 後ろからDPテーブルを埋める
    for (int i = n - 3; i >= 0; i--) {
        maxSumDP[i] = max(arr[i] + maxSumDP[i + 2],
                          maxSumDP[i + 1]);
    }
    return maxSumDP[0];
}

int main() {
    vector<int> arr = { 5, 2, 1, 9, 6 };
    int n = arr.size();
    cout << "隣接する要素を同時に選ばない場合の最大部分列和: "
         << calcMaxSum(arr, n) << endl;
    return 0;
}

実行結果

隣接する要素を同時に選ばない場合の最大部分列和: 14

計算量

• 時間計算量: O(n) — 配列を1回走査するだけで完了します。
• 空間計算量: O(n) — DPテーブル用の配列が必要です。

まとめ

「隣接する要素を同時に選べない」という制約付きの最大和問題は、動的計画法を使うことで線形時間 O(n) で効率的に解くことができます。各位置で「その要素を選ぶか / 選ばないか」の2択を比較するシンプルな漸化式がポイントです。このパターンは、ハウスロバー問題など他の有名なDP問題にも応用できる重要な考え方なので、ぜひマスターしておきましょう。