C++で指定された数まで配列要素を最大化します

整数、数値、および最大値の配列が与えられた場合、タスクは配列要素から取得できる最大値を計算することです。最初からトラバースする配列のすべての値は、前のインデックスから取得した結果に加算または減算して、任意の時点で結果が0以上、指定された最大値以下になるようにすることができます。インデックス0の場合、指定された数に等しい前の結果を取得します。可能な回答がない場合は-1を印刷します。

arr [] ={3、10、6、4、5}、数値=1、最大値=15の場合、加算と減算の順序に従うと、出力は9になります-

1 + 3 + 10 – 6 – 4 + 5

アルゴリズム

この問題を解決するために再帰的アプローチを使用できます

1. At every index position there are two choices, either add current array element to value obtained so far from previous elements or subtract current array element from value obtained so far from previous elements
2. Start from index 0, add or subtract arr[0] from given number and recursively call for next index along with updated number
3. When entire array is traversed, compare the updated number with overall maximum value of number obtained so far

例

#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