সমস্যা বিবৃতি
একটি অ্যারে arr[] দেওয়া. উপসর্গ যোগফলের সর্বাধিক মান খুঁজুন যা সূচক i in arr[]-এর জন্য প্রত্যয় যোগফলও।
উদাহরণ
যদি ইনপুট অ্যারে −
হয়Arr[] ={1, 2, 3, 5, 3, 2, 1} তাহলে আউটপুট হল 11 হিসাবে −
- উপসর্গ যোগফল =arr[0..3] =1 + 2 + 3 + 5 =11 এবং
- প্রত্যয় যোগফল =arr[3..6] =5 + 3 + 2 + 1 =11
অ্যালগরিদম
- অ্যারে অতিক্রম করুন এবং অ্যারে প্রিসাম[]-এ প্রতিটি সূচকের উপসর্গের যোগফল সংরক্ষণ করুন, যেখানে প্রিসাম[i] সাবয়ারের অ্যারের যোগফল সংরক্ষণ করে[0..i]
- আবার অ্যারে ট্র্যাভার্স করুন এবং প্রত্যয় যোগফলকে অন্য অ্যারের সাফসাম[]-এ সঞ্চয় করুন, যেখানে সাফসাম[i] সাবয়ারের অ্যারের যোগফল সংরক্ষণ করে[i..n-1]
- প্রতিটি সূচকের জন্য পরীক্ষা করুন যে presum[i] suffsum[i] এর সমান এবং যদি তারা সমান হয় তবে তুলনা করুন, এখন পর্যন্ত সামগ্রিক সর্বাধিকের সাথে মান আছে
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
int preSum[n];
int suffSum[n];
int result = INT_MIN;
preSum[0] = arr[0];
for (int i = 1; i < n; ++i) {
preSum[i] = preSum[i - 1] + arr[i];
}
suffSum[n - 1] = arr[n - 1];
if (preSum[n - 1] == suffSum[n - 1]) {
result = max(result, preSum[n - 1]);
}
for (int i = n - 2; i >= 0; --i) {
suffSum[i] = suffSum[i + 1] + arr[i];
if (suffSum[i] == preSum[i]) {
result = max(result, preSum[i]);
}
}
return result;
}
int main() {
int arr[] = {1, 2, 3, 5, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max equlibrium sum = " << getMaxSum(arr, n) << endl;
return 0;
} আউটপুট
আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেMax equlibrium sum = 11
