数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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
更新于：2019年12月24日
394 次查看
广告