資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告