সমস্যা বিবরণ
একটি অ্যারে arr[] দেওয়া আছে। অ্যারের i ইনডেক্সে প্রিফিক্স যোগফল ও সাফিক্স যোগফল সমান হলে তার সর্বোচ্চ মান বের করুন।
উদাহরণ
ইনপুট অ্যারে যদি −
Arr[] = {1, 2, 3, 5, 3, 2, 1} হয়, তবে আউটপুট হবে ১১ কারণ −
- প্রিফিক্স যোগফল = arr[0..3] = 1 + 2 + 3 + 5 = 11 এবং
- সাফিক্স যোগফল = arr[3..6] = 5 + 3 + 2 + 1 = 11
অ্যালগরিদম
- অ্যারে ট্রাভার্স করে প্রতিটি ইনডেক্সের প্রিফিক্স যোগফল presum[] অ্যারেতে সংরক্ষণ করুন, যেখানে presum[i] ধারণ করে arr[0..i]-র সাব-অ্যারের যোগফল
- আবার অ্যারে ট্রাভার্স করে সাফিক্স যোগফল suffsum[] অ্যারেতে সংরক্ষণ করুন, যেখানে suffsum[i] ধারণ করে arr[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
