এই সমস্যাতে, আমাদের একটি সার্কুলার অ্যারে cirArr[] দেওয়া আছে। আমাদের কাজ হল C++-এ এমন একটি প্রোগ্রাম তৈরি করা যাতে সার্কুলার অ্যারেতে আঁচবিক (adjacent) কোনো দুটি উপাদান না নেওয়া শর্তে সর্বোচ্চ যোগফল বের করা যায়।
সমস্যার বিবরণ
সার্কুলার অ্যারেতে আমাদের উপাদানগুলোর সর্বোচ্চ যোগফল বের করতে হবে যাতে আঁচবিক উপাদানগুলো একসাথে নেওয়া যায় না, অর্থাৎ আমাদের বारी বاری উপাদান নিতে হবে।
সার্কুলার অ্যারে হল একটি বিশেষ ধরনের অ্যারে যেখানে অ্যারেটিয়ের শেষ উপাদানটি প্রথম উপাদানের সাথে সংযুক্ত থাকে।
উদাহরণ
ইনপুট
cirArr[] = {4, 1, 5, 3, 2}
আউটপুট
9
ব্যাখ্যা
সর্বোচ্চ যোগফল দেয় এমন সার্কুলার সাবসিকোয়েন্স হল [4, 5, 2]। যোগফল = 9
সমাধানের পদ্ধতি
এই সমস্যার সমাধান হল ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করে সর্বোচ্চ যোগফল বের করা। সার্কুলার অ্যারেকে দুটি আলাদা অ্যারে হিসেবে বিবেচনা করা হয়: একটি ইনডেক্স 0 থেকে N-2 পর্যন্ত এবং অন্যটি ইনডেক্স 1 থেকে N-1 পর্যন্ত। এই দুটি অ্যারের থেকে পাওয়া যোগফলগুলোর মধ্যে সর্বোচ্চটি ही ফলাফল হবে।
প্রোগ্রাম উদাহরণ
নিচের প্রোগ্রামটি সমাধানের কাজকর্ম প্রদর্শন করে:
#include <iostream>
using namespace std;
int calcMaxVal(int a, int b) {
if (a > b)
return a;
return b;
}
int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
int DP[n];
int maxSum = 0;
for (int i = start; i < (end + 1); i++) {
DP[i] = cirArr[i];
if (maxSum < cirArr[i])
maxSum = cirArr[i];
}
for (int i = (start + 2); i < (end + 1); i++) {
for (int j = 0; j < i - 1; j++) {
if (DP[i] < DP[j] + cirArr[i]) {
DP[i] = DP[j] + cirArr[i];
if (maxSum < DP[i])
maxSum = DP[i];
}
}
}
return maxSum;
}
int findMaxSum(int cirArr[], int n) {
int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n - 2), n);
int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n - 1), n);
int maxSum = calcMaxVal(maxSumArray1, maxSumArray2);
return maxSum;
}
int main() {
int cirArr[] = {4, 1, 5, 3, 2};
int n = sizeof(cirArr) / sizeof(cirArr[0]);
cout << "The maximum sum in circular array such that no two elements are adjacent is " << findMaxSum(cirArr, n);
return 0;
}
আউটপুট
The maximum sum in circular array such that no two elements are adjacent is 9
