এই সমস্যায়, আমাদের একটি অ্যারে দেওয়া হয়েছে arr[]। আমাদের কাজ হল সর্বাধিক যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা যাতে C++ এ দুটি উপাদান সংলগ্ন না থাকে।
সমস্যা বর্ণনা
আমাদের অ্যারে থেকে ক্রমটির সর্বাধিক যোগফল খুঁজে বের করতে হবে যাতে যোগফলের ক্রম থেকে কোনও 2 সংখ্যা অ্যারের সংলগ্ন না হয়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {5, 1, 3, 7, 9, 2, 5} আউটপুট
22
ব্যাখ্যা
Taking sum sequence from index 0 with alternate elements : 5 + 3 + 9 + 5 = 22 Taking sum sequence from index 1 with alternate elements : 1 + 7 + 2 = 10
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমরা কেবল অ্যারের সমস্ত উপাদান লুপ করব এবং দুটি যোগফল বজায় রাখব। sumVar1 এবং sumVar2, sumVar1 বর্তমান উপাদানের সাথে যোগফল অন্তর্ভুক্ত করবে এবং sumVar2 বর্তমান উপাদান ছাড়া যোগফল অন্তর্ভুক্ত করবে।
প্রতিটি পুনরাবৃত্তির সাথে, আমরা sumVar2 কে max(sumVar1, sumVar2) হিসাবে আপডেট করব। এবং তারপর sumVar1 আপডেট করুন। লুপের শেষে, sumVar2 প্রয়োজনীয় যোগফল দেবে।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include<iostream>
using namespace std;
int findmaximum(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxSumWOAdjecent(int arr[], int N){
int maxSum1 = arr[0];
int maxSum2 = 0;
int temp;
for (int i = 1; i < N; i++) {
temp = findmaximum(maxSum1, maxSum2);
maxSum1 = maxSum2 + arr[i];
maxSum2 = temp;
}
return (findmaximum(maxSum1, maxSum2));
}
int main(){
int arr[] = {5, 1, 3, 7, 9, 2, 5};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum such that no two elements are adjacent is "<<findMaxSumWOAdjecent(arr, N);
return 0;
} আউটপুট
The maximum sum such that no two elements are adjacent is 22
