C++ में दिए गए नंबर तक ऐरे तत्वों को अधिकतम करना

समस्या कथन

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

यदि arr[] = {3, 10, 6, 4, 5}, संख्या = 1 और अधिकतम मान = 15 तो आउटपुट 9 होगा यदि हम नीचे दिए गए जोड़ और घटाव के क्रम का पालन करें:

1 + 3 + 10 - 6 - 4 + 5

एल्गोरिदम

हम इस समस्या को हल करने के लिए पुनरावर्ती दृष्टिकोण का उपयोग कर सकते हैं:

1. प्रत्येक इंडेक्स स्थिति पर दो विकल्प हैं, या तो वर्तमान ऐरे तत्व को पिछले तत्वों से अब तक प्राप्त मान में जोड़ें या वर्तमान ऐरे तत्व को पिछले तत्वों से अब तक प्राप्त मान से घटाएं।
2. इंडेक्स 0 से शुरू करें, दी गई संख्या से arr[0] जोड़ें या घटाएं और अद्यतन संख्या के साथ अगले इंडेक्स के लिए पुनरावर्ती कॉल करें।
3. जब पूरा ऐरे पार हो जाए, तो अद्यतन संख्या की तुलना अब तक प्राप्त संख्या के समग्र अधिकतम मान से करें।

उदाहरण

#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