Tuyên bố vấn đề
Cho một mảng các số nguyên, một số và một giá trị lớn nhất, nhiệm vụ là tính giá trị lớn nhất có thể nhận được từ các phần tử của mảng. Mọi giá trị trên mảng đi qua từ đầu có thể được cộng hoặc trừ khỏi kết quả thu được từ chỉ mục trước đó sao cho kết quả tại bất kỳ thời điểm nào không nhỏ hơn 0 và không lớn hơn giá trị lớn nhất đã cho. Đối với chỉ số 0 lấy kết quả trước đó bằng số đã cho. Trong trường hợp không thể trả lời, hãy in -1.
Nếu arr [] ={3, 10, 6, 4, 5}, number =1 và max value =15 thì đầu ra sẽ là 9 nếu tuân theo thứ tự dưới đây của phép cộng và phép chia -
1 + 3 + 10 – 6 – 4 + 5
Thuật toán
Chúng ta có thể sử dụng phương pháp đệ quy để giải quyết vấn đề này
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
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau−
Maximum value = 9