সমস্যা বিবরণ
n সংখ্যক পজিটিভ এলিমেন্টের একটি অ্যারে দেওয়া আছে। আমাদের কাজ হল সাবঅ্যারেতে max এবং min এলিমেন্টের যোগফলের ন্যূনতম সম্ভাব্য মান খুঁজে বের করা, শর্ত হল সাবঅ্যারের সাইজ কমপক্ষে ২ হতে হবে।
উদাহরণ
যদি arr[] = {10, 5, 15, 7, 2, 1, 3} হয়, তবে "max + min" এর যোগফল ৩ হবে যখন আমরা "2 + 1" করব।
অ্যালগরিদম
- সাবঅ্যারেতে যেকোনো এলিমেন্ট যোগ করলে max এবং min-এর যোগফল বাড়বে না।
- যেহেতু একটি অ্যারের max মান নতুন এলিমেন্ট যোগ করলে কখনো কমে না (শুধু বড় এলিমেন্ট যোগ করলে বাড়ে), তাই সর্বোত্তম হবে শুধু লেন্থ ২-এর সাবঅ্যারেগুলো বিবেচনা করা।
- অতএব লেন্থ ২-এর সব সাবঅ্যারে বিবেচনা করে যোগফল তুলনা করুন এবং ন্যূনতমটি নিন।
সি++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int* arr, int n) {
if (n < 2) return -1;
int result = arr[0] + arr[1];
for (int i = 1; i + 1 < n; ++i)
result = min(result, (arr[i] + arr[i + 1]));
return result;
}
int main() {
int arr[] = {10, 5, 15, 7, 2, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
return 0;
}
আউটপুট
Maximum sum = 3
