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