C++で配列要素の加減算により指定範囲内の最大値を求める方法

問題文

整数の配列、初期値となる数値、および最大値が与えられます。配列の要素を先頭から順に走査し、各要素について「現在の結果に加算する」か「減算する」かを選択します。ただし、どの時点でも結果は 0 以上かつ最大値以下でなければなりません。インデックス 0 の処理では、与えられた数値を初期結果として扱います。条件を満たす答えが存在しない場合は -1 を出力します。

例として、arr[] = {3, 10, 6, 4, 5}、number = 1、最大値 = 15 が与えられた場合、次の順序で加算・減算を行うと出力は 9 になります。

1 + 3 + 10 - 6 - 4 + 5

アルゴリズム

この問題は再帰的なアプローチで解くことができます。

1. 各インデックスには2つの選択肢があります。これまでの要素から得られた値に現在の配列要素を加算するか、減算するかのどちらかです。
2. インデックス0から開始し、与えられた数値に arr[0] を加算または減算して、更新された数値とともに次のインデックスを再帰的に呼び出します。
3. 配列全体の走査が完了したら、更新された数値をこれまでに得られた全体の最大値と比較します。

実装例

以下は、上記のアルゴリズムを C++ で実装した例です。

#include <bits/stdc++.h>
using namespace std;
void getMaxValue(int *arr, int n, int num, int maxLimit, int idx, int& result){
    if (idx == n) {
        result = max(result, num);
        return;
    }
    if (num - arr[idx] >= 0) {
        getMaxValue(arr, n, num - arr[idx], maxLimit, idx + 1, result);
    }
    if (num + arr[idx] <= maxLimit) {
        getMaxValue(arr, n, num + arr[idx], maxLimit, idx + 1, result);
    }
}
int getMaxValue(int *arr, int n, int num, int maxLimit){
    int result = 0;
    int idx = 0;
    getMaxValue(arr, n, num, maxLimit, idx, result);
    return result;
}
int main(){
    int num = 1;
    int arr[] = {3, 10, 6, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxLimit = 15;
    cout << "Maximum value = " << getMaxValue(arr, n, num, maxLimit) << endl;
    return 0;
}

出力

上記のプログラムをコンパイルして実行すると、次の出力が生成されます。

Maximum value = 9

計算量について

各インデックスで最大2つの分岐が生じるため、この再帰解法の時間計算量は O(2^n) となります。空間計算量は再帰スタックの深さに比例し、O(n) です。配列サイズが大きくなる場合は、メモ化や動的計画法を組み合わせることで効率化を図ることができます。