जोड़े की एक श्रृंखला दी गई है। प्रत्येक जोड़ी में दो पूर्णांक होते हैं और पहला पूर्णांक हमेशा छोटा होता है, और दूसरा बड़ा होता है, वही नियम श्रृंखला निर्माण के लिए भी लागू किया जा सकता है। एक जोड़ी (x, y) को एक जोड़ी (p, q) के बाद जोड़ा जा सकता है, केवल अगर q
इस समस्या को हल करने के लिए, पहले हमें दिए गए युग्मों को पहले तत्व के बढ़ते क्रम में क्रमबद्ध करना होगा। उसके बाद हम जोड़ी के दूसरे तत्व की तुलना अगले जोड़े के पहले तत्व से करेंगे।
इनपुट - संख्या जोड़े की एक श्रृंखला। {(5, 24), (15, 25), (27, 40), (50, 60)}
आउटपुट - दिए गए मानदंड के अनुसार श्रृंखला की सबसे बड़ी लंबाई। यहाँ लंबाई 3 है।एल्गोरिदम
maxChainLength(arr, n)
each element of chain will contain two elements a and b
Input: The array of pairs, number of items in the array.
Output: Maximum length.
Begin
define maxChainLen array of size n, and fill with 1
max := 0
for i := 1 to n, do
for j := 0 to i-1, do
if arr[i].a > arr[j].b and maxChainLen[i] < maxChainLen[j] + 1
maxChainLen[i] := maxChainLen[j] + 1
done
done
max := maximum length in maxChainLen array
return max
End
उदाहरण
#include<iostream>
#include<algorithm>
using namespace std;
struct numPair{ //define pair as structure
int a;
int b;
};
int maxChainLength(numPair arr[], int n){
int max = 0;
int *maxChainLen = new int[n]; //create array of size n
for (int i = 0; i < n; i++ ) //Initialize Max Chain length values for all indexes
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;
// maxChainLen[i] now holds the max chain length ending with pair i
for (int i = 0; i < n; i++ )
if ( max < maxChainLen[i] )
max = maxChainLen[i]; //find maximum among all chain length values
delete[] maxChainLen; //deallocate memory
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
