【C++】同じ配列を連続して選べない条件で3つの配列から得られる最大合計の求め方

この記事では、サイズ N の3つの配列 arr1[]、arr2[]、arr3[] が与えられたとき、「同じ配列からは連続して要素を選べない」という制約のもとで、合計の最大値を求めるプログラムをC++で作成する方法を解説します。

問題の概要

N個の要素を選んで合計を最大化します。i 番目に選べる要素は、各配列の i 番目の要素、すなわち arr1[i]、arr2[i]、arr3[i] のいずれか1つです。重要な制約として、隣り合う位置で同じ配列から2回続けて要素を選ぶことはできません。

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

入力例

arr1[] = {5, 8, 9, 20},
arr2[] = {7, 12, 1, 10},
arr3[] = {8, 9, 10, 11}
N = 4

出力例

50

説明

各位置で次のように要素を選びます。

• i = 1: arr3 の 8 を選択
• i = 2: arr2 の 12 を選択
• i = 3: arr3 の 10 を選択
• i = 4: arr1 の 20 を選択

合計 = 8 + 12 + 10 + 20 = 50 となり、これが制約を満たす最大の合計です。

解法アプローチ：動的計画法（メモ化）

この問題は動的計画法（DP）で効率的に解けます。重複した計算を避けるために、各状態の結果をメモ化しておくのがポイントです。

具体的には、2次元配列 DP[][] を用意します。DP[i][j] には「i 番目までの位置で j 番目の配列を選んだ場合の最大合計」を格納します。再帰的に現在位置の要素を確定させたら、その次の要素は残りの2つの配列から選ぶよう処理を分岐させます。

アルゴリズムの手順

1. 開始位置 index = 0 に対して、3つの配列それぞれから始まるケースを計算します。
2. 各再帰呼び出しでは、直前に使った配列以外の2つの配列から次の要素を選んだ場合の合計を比較し、大きい方を採用します。
3. すでに計算済みの状態（DP[index][arrNo] != -1）は、メモ化された値をそのまま返して計算量を削減します。
4. 最後に、3つの開始パターンの中で最大の値が答えになります。

実装例

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

#include <bits/stdc++.h>
using namespace std;
const int N = 3;

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

int FindMaximumSum(int index, int arrNo, int arr1[], int arr2[], int arr3[], int n, int DP[][N]){
    // 配列の末尾に到達したら合計は 0
    if (index == n)
        return 0;
    // 計算済みの状態ならメモ化した値を返す
    if (DP[index][arrNo] != -1)
        return DP[index][arrNo];

    int maxVal = -1;

    if (arrNo == 0){
        maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
        maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
    }
    else if (arrNo == 1){
        maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
        maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
    }
    else if (arrNo == 2){
        maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
        maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
    }

    return DP[index][arrNo] = maxVal;
}

int main(){
    int arr1[] = { 5, 8, 9, 20 };
    int arr2[] = { 7, 12, 1, 10 };
    int arr3[] = { 8, 9, 10, 11 };

    int n = sizeof(arr1) / sizeof(arr1[0]);

    int DP[n][N];
    memset(DP, -1, sizeof DP);

    int val1 = FindMaximumSum(0, 0, arr1, arr2, arr3, n, DP);
    int val2 = FindMaximumSum(0, 1, arr1, arr2, arr3, n, DP);
    int val3 = FindMaximumSum(0, 2, arr1, arr2, arr3, n, DP);

    cout<<"同じ配列から連続して要素を選択しない場合の3つの配列の最大合計は "
       <<findMaxVal(val1, findMaxVal(val2, val3));

    return 0;
}

出力

同じ配列から連続して要素を選択しない場合の3つの配列の最大合計は 50

計算量について

状態 (index, arrNo) の組み合わせは高々 3 × N 個しか存在せず、それぞれが一度しか計算されないため、時間計算量は O(N)、DPテーブルの分だけ空間計算量も O(N) となります。すべての選び方を総当たりで調べるアプローチと比べて大幅に効率的である点が、メモ化再帰（トップダウン型DP）を用いる大きなメリットです。