C++ में दिए गए नंबरों तक सरणी तत्वों को अधिकतम करें

समस्या कथन

पूर्णांकों की एक सरणी, एक संख्या और एक अधिकतम मान को देखते हुए, कार्य उस अधिकतम मान की गणना करना है जो सरणी तत्वों से प्राप्त किया जा सकता है। शुरुआत से ट्रैवर्सिंग एरे पर प्रत्येक मान को पिछले इंडेक्स से प्राप्त परिणाम से जोड़ा या घटाया जा सकता है जैसे कि किसी भी बिंदु पर परिणाम 0 से कम नहीं होता है और दिए गए अधिकतम मूल्य से अधिक नहीं होता है। सूचकांक 0 के लिए पिछले परिणाम को दी गई संख्या के बराबर लें। उत्तर प्रिंट न होने की स्थिति में -1.

अगर एआर [] ={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