নির্দিষ্ট পার্থক্য C++ প্রোগ্রাম সহ জোড়ার সর্বোচ্চ যোগফল

এই সমস্যায়, আমাদেরকে n পূর্ণসংখ্যার একটি অ্যারে [] এবং একটি সংখ্যা দেওয়া হয়েছে। .

সমস্যা বর্ণনা − আমরা এমনভাবে জোড়া খুঁজে পাব যাতে জোড়ার উপাদানের পার্থক্য d-এর থেকে কম হয়। এই ধরনের সব জোড়ার যোগফল সর্বাধিক হওয়া উচিত।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট

arr[] ={5, 9, 11, 7, 2, 12, 3} d =5

আউটপুট

47

ব্যাখ্যা

জোড়া যেগুলি সর্বাধিক যোগফলের জন্য অবদান রাখে:(3, 5), (7, 9), (11, 12)। যোগফল =3 + 5 + 7 + 9 + 11 + 12 =47

সমাধান পদ্ধতি

সমস্যার একটি সহজ এবং সুস্পষ্ট সমাধান হল অ্যারের সমস্ত বৈধ জোড়া তৈরি করা এবং তারপর যোগফল খুঁজে বের করা এবং সমস্ত যোগফলের সর্বাধিক ফেরত দেওয়া। কিন্তু এই সমাধান কার্যকর নয়।

একটি ডায়নামিক প্রোগ্রামিং অ্যাপ্রোচ ব্যবহার করে সমস্যার একটি কার্যকর সমাধান। এখানে, আমরা সর্বোত্তম জোড়া খুঁজে পাব যা একটি সর্বাধিক যোগফল গঠন করে। এর জন্য আমরা একটি সাজানো অ্যারে ব্যবহার করব, তাই প্রথমে আমরা প্রদত্ত অ্যারে সাজাব এবং তারপরে এটি পরিচালনা করব। যোগফল খুঁজে বের করার জন্য, বর্তমান উপাদান পর্যন্ত জোড়ার সর্বোচ্চ যোগফল সংরক্ষণ করতে আমরা একটি অ্যারে ব্যবহার করব। এর জন্য, আমরা বর্তমান উপাদান এবং পূর্ববর্তী উপাদানগুলি একটি জোড়া তৈরি করে কিনা তা পরীক্ষা করব। যদি হ্যাঁ, আমরা অ্যারে পর্যন্ত maxSum-এ জোড়া যোগ করব। অন্যথায়, ম্যাক্সসাম যেমন আছে তেমনই থাকবে।

অ্যালগরিদম

শুরু করুন:DP[n]

ধাপ 1 −

অ্যারে অ্যারের জন্য[]।

ধাপ 2

DP[0] =0;

ধাপ 3 −

 i −> 1 থেকে n

ধাপ ৩.১ −

যদি হ্যাঁ, বর্তমান জোড়ের যোগফল শেষ বিবেচিত যোগফলের চেয়ে বেশি মান দেখায় কিনা এবং বর্তমান যোগফলের সর্বোচ্চ মান যোগ করুন। যেমন যদি( (DP[i−2] + arr[i−1] + arr[i])> (DP[i−1]) −>DP[i] =(DP[i−2] + arr[ i−1] + arr[i]), অন্যথায় −> DP[i] =DP[i−1]।

একটি ব্যতিক্রম হল i =1 মানের জন্য, যেখানে DP[i−2] এর কোনো মান সম্ভব নয়, এই ক্ষেত্রে, DP[i−2] কে প্রথম জোড়া হিসাবে বিবেচনা করা হয় না।

রিটার্ন DP[n−1] .

#include নেমস্পেস ব্যবহার করে std;int CalcmaxPairSum(int arr[], int n, int d) { sort(arr, arr+n); int maxSumDP[n]; maxSumDP[0] =0; জন্য (int i =1; i =2) if(maxSumDP[i] <(maxSumDP[i−2] + arr[i−1] + arr[i] )) maxSumDP[i] =(maxSumDP[i−2] + arr[i−1] + arr[i]); অন্যথায় যদি(maxSumDP[i] <(arr[i−1] + arr[i])) maxSumDP[i] =arr[i−1] + arr[i]; } } রিটার্ন maxSumDP[n−1];}int main() { int arr[] ={5, 9, 11, 7, 2, 12, 3}; int n =7, d =5; cout<<"নির্দিষ্ট পার্থক্য সহ জোড়ার সর্বোচ্চ যোগফল হল "< 
আউটপুট
 
নির্দিষ্ট পার্থক্য সহ জোড়ার সর্বোচ্চ যোগফল হল 47