সমস্যা বিবরণ
একটি ইন্টিজার অ্যারে, একটি সংখ্যা এবং একটি সর্বোচ্চ মান দেওয়া আছে। কাজ হল অ্যারে উপাদান থেকে প্রাপ্ত সর্বোচ্চ মান গণনা করা। অ্যারেটি শুরু থেকে ট্রভার্স করার সময় প্রতিটি মান আগের ইন্ডেক্স থেকে প্রাপ্ত ফলাফলের সাথে বা যোগ করা যাবে বা বিয়োগ করা যাবে যেন যেকোনো পয়েন্টে ফলাফল ০-এর চেয়ে কম না হয় এবং দেওয়া সর্বোচ্চ মানের চেয়ে বেশি না হয়। ইন্ডেক্স ০-এর জন্য আগের ফলাফল দেওয়া সংখ্যা ধরা হবে। কোনো সম্ভাব্য উত্তর না থাকলে -1 প্রিন্ট করুন।
যদি arr[] = {3, 10, 6, 4, 5}, number = 1 এবং max value = 15 হয় তবে আউটপুট হবে ৯ যদি নিচের যোগ ও বিয়োগের ক্রম ফলো করা হয়:
1 + 3 + 10 - 6 - 4 + 5
অ্যালগরিদম
এই সমস্যা সমাধানের জন্য রিকার্সিভ পদ্ধতি ব্যবহার করা যায়:
1. প্রতিটি ইন্ডেক্স পজিশনে দুটি অপশন আছে: বর্তমান অ্যারে উপাদানটি আগের উপাদানlardan প্রাপ্ত মানের সাথে যোগ করা অথবা বিয়োগ করা। 2. ইন্ডেক্স ০ থেকে শুরু করুন, 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
