【C++】循環配列で隣接しない要素を選んだときの最大合計を求める方法

問題の概要

本記事では、循環配列 cirArr[] が与えられたとき、「どの2つの要素も隣接して選ばない」という条件を満たす要素の最大合計を求めるプログラムをC++で作成します。

問題の詳細

循環配列に対して、隣接する要素を同時に選ぶことができない、つまり要素を一つ飛ばしで選択した場合の最大合計を求める必要があります。

循環配列とは、配列の末尾の要素が先頭の要素につながっている特殊な配列構造のことです。

具体例で問題を確認しましょう。

入力例

cirArr[] = {4, 1, 5, 3, 2}

出力例

9

解説

最大の合計となる循環部分列は [4, 5, 2] で、その合計は 9 になります。

解決アプローチ

この問題は、動的計画法(DP)を用いることで効率的に解くことができます。ポイントは、循環配列を次の2つの線形配列に分解して考えることです。

• インデックス 0 から N-2 までの配列(末尾の要素を除外)
• インデックス 1 から N-1 までの配列(先頭の要素を除外)

それぞれの配列について「隣接しない要素の最大合計」を計算し、2つの結果のうち大きい方を答えとします。これにより、循環構造特有の「先頭と末尾が隣接する」という制約の矛盾を回避できます。

C++実装例

以下は、この解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;

int calcMaxVal(int a, int b){
    if(a > b)
        return a;
    return b;
}

// 指定範囲内で隣接しない要素の最大合計をDPで求める
int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
    int DP[n];
    int maxSum = 0;
    // DPテーブルの初期化
    for (int i = start; i < (end + 1); i++) {
        DP[i] = cirArr[i];
        if (maxSum < cirArr[i])
            maxSum = cirArr[i];
    }
    // 動的計画法で最大合計を更新
    for (int i = (start + 2); i < (end + 1); i++) {
        for (int j = 0; j < i - 1; j++) {
            if (DP[i] < DP[j] + cirArr[i]) {
                DP[i] = DP[j] + cirArr[i];
                if (maxSum < DP[i])
                    maxSum = DP[i];
            }
        }
    }
    return maxSum;
}

int findMaxSum(int cirArr[], int n){
    // 循環配列を2つの線形配列に分割して処理
    int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n-2), n);
    int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n-1), n);
    return calcMaxVal(maxSumArray1, maxSumArray2);
}

int main(){
    int cirArr[] = {4, 1, 5, 3, 2};
    int n = sizeof(cirArr)/sizeof(cirArr[0]);
    cout<<"隣接しない要素を選んだ循環配列の最大合計は "<<findMaxSum(cirArr, n);
    return 0;
}

実行結果

隣接しない要素を選んだ循環配列の最大合計は 9

まとめ

循環配列で隣接しない要素の最大合計を求める問題は、配列を2つの線形配列に分割して動的計画法を適用することで解けます。上記の実装の計算量は O(N²) です。なお、各位置における「選ぶ/選ばない」の状態遷移を管理する方式(家屋強盗問題と同様のアプローチ)を採用すれば、O(N) まで計算量を抑えることも可能です。まずは本記事の手法で循環配列の性質とDPの考え方を理解するのがおすすめです。