在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