একটি পেয়ার চেইন দেওয়া আছে। প্রতিটি পেয়ারে দুটি পূর্ণসংখ্যা থাকে এবং প্রথম পূর্ণসংখ্যাটি সবসময় ছোট, দ্বিতীয়টি বড়। চেইন গঠনের জন্যও একই নিয়ম প্রয়োগ করা হয়। একটি পেয়ার (x, y) কোনো পেয়ার (p, q)-এর পরে যোগ করা যাবে, শুধু যদি q < x হয়।
এই সমস্যা সমাধান করতে প্রথমে দেয়া পেয়ারগুলো প্রথম উপাদান অনুযায়ী ক্রমবর্ধমান ক্রমে সর্ট করতে হয়। তারপর একটি পেয়ারের দ্বিতীয় উপাদানকে পরের পেয়ারের প্রথম উপাদানের সাথে তুলনা করা হয়।
ইনপুট এবং আউটপুট
ইনপুট: সংখ্যা পেয়ারের একটি চেইন।
{(5, 24), (15, 25), (27, 40), (50, 60)}
আউটপুট: দেয়া শর্তানুযায়ী চেইনের সর্বোচ্চ দৈর্ঘ্য। এখানে দৈর্ঘ্য ৩।
অ্যালগরিদম
maxChainLength(arr, n)
চেইনের প্রতিটি উপাদান a এবং b দুটি উপাদান ধারণ করবে।
ইনপুট: পেয়ারগুলোর অ্যারে, অ্যারেতে আইটেম সংখ্যা।
আউটপুট: সর্বোচ্চ দৈর্ঘ্য।
শুরু
n আকারের maxChainLen অ্যারে সংজ্ঞায়িত করুন এবং ১ দিয়ে পূরণ করুন
max := 0
i := 1 থেকে n পর্যন্ত, করুন
j := 0 থেকে i-1 পর্যন্ত, করুন
যদি arr[i].a > arr[j].b এবং maxChainLen[i] < maxChainLen[j] + 1 হয়, তবে
maxChainLen[i] := maxChainLen[j] + 1
শেষ
শেষ
max := maxChainLen অ্যারেতে সর্বোচ্চ দৈর্ঘ্য
max ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
#include <algorithm>
using namespace std;
struct numPair {
int a;
int b;
};
int maxChainLength(numPair arr[], int n) {
int max = 0;
int *maxChainLen = new int[n];
for (int i = 0; i < n; i++)
maxChainLen[i] = 1;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i].a > arr[j].b && maxChainLen[i] < maxChainLen[j] + 1)
maxChainLen[i] = maxChainLen[j] + 1;
for (int i = 0; i < n; i++)
if (max < maxChainLen[i])
max = maxChainLen[i];
delete[] maxChainLen;
return max;
}
int main() {
struct numPair arr[] = {{5, 24},{15, 25},{27, 40},{50, 60}};
int n = 4;
cout << "Length of maximum size chain is " << maxChainLength(arr, n);
}
আউটপুট
Length of maximum size chain is 3
