打印双链的最大长度-yiteyi-C++库

给你n对数字。在每一对中，第一个数字总是小于第二个数字。如果b

null

例如：

Input:  (5, 24), (39, 60), (15, 28), (27, 40), (50, 90)
Output: (5, 24), (27, 40), (50, 90)

Input:  (11, 20), {10, 40), (45, 60), (39, 40)
Output: (11, 20), (39, 40), (45, 60)

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

在里面以前的在这篇文章中，我们讨论了最大长度的成对链问题。然而，这篇文章只涉及与寻找最大尺寸链长度有关的代码，而不涉及最大尺寸链的构造。在这篇文章中，我们将讨论如何构造成对的最大长度链。

其思想是首先按照给定对的第一个元素的递增顺序对它们进行排序。设arr[0..n-1]为排序后的成对输入数组。我们定义了向量L，使得L[i]本身是一个向量，它存储以arr[i]结尾的arr[0..i]对的最大长度链。因此，对于索引i，L[i]可以递归地写为——

L[0] = {arr[0]}
L[i] = {Max(L[j])} + arr[i] where j < i and arr[j].b < arr[i].a 
     = arr[i], if there is no such j

例如，对于（5,24）、（39,60）、（15,28）、（27,40）、（50,90）

L[0]: (5, 24)
L[1]: (5, 24) (39, 60)
L[2]: (15, 28)
L[3]: (5, 24) (27, 40)
L[4]: (5, 24) (27, 40) (50, 90)

请注意，配对的排序已经完成，因为我们需要找到最大配对长度，这里的排序并不重要。如果我们不排序，我们将以递增的顺序得到对，但它们不会是最大可能的对。

以下是上述理念的实施——

C++

                             /* Dynamic Programming solution to construct                           
                                                         Maximum Length Chain of Pairs */                           
                             #include <bits/stdc++.h>                           
                             using                                           namespace                                           std;                           
                                         
                             struct                                           Pair                           
                             {                           
                                                         int                                           a;                           
                                                         int                                           b;                           
                             };                           
                                         
                             // comparator function for sort function                           
                             int                                           compare(Pair x, Pair y)                           
                             {                           
                                                         return                                           x.a < y.a;                           
                             }                           
                                         
                             // Function to construct Maximum Length Chain                           
                             // of Pairs                           
                             void                                           maxChainLength(vector<Pair> arr)                           
                             {                           
                                                         // Sort by start time                           
                                                         sort(arr.begin(), arr.end(), compare);                           
                                         
                                                         // L[i] stores maximum length of chain of                           
                                                         // arr[0..i] that ends with arr[i].                           
                                                         vector<vector<Pair> > L(arr.size());                           
                                         
                                                         // L[0] is equal to arr[0]                           
                                                         L[0].push_back(arr[0]);                           
                                         
                                                         // start from index 1                           
                                                         for                                           (                                           int                                           i = 1; i < arr.size(); i++)                           
                                                         {                           
                                                         // for every j less than i                           
                                                         for                                           (                                           int                                           j = 0; j < i; j++)                           
                                                         {                           
                                                         // L[i] = {Max(L[j])} + arr[i]                           
                                                         // where j < i and arr[j].b < arr[i].a                           
                                                         if                                           ((arr[j].b < arr[i].a) &&                           
                                                         (L[j].size() > L[i].size()))                           
                                                         L[i] = L[j];                           
                                                         }                           
                                                         L[i].push_back(arr[i]);                           
                                                         }                           
                                         
                                                         // print max length vector                           
                                                         vector<Pair> maxChain;                           
                                                         for                                           (vector<Pair> x : L)                           
                                                         if                                           (x.size() > maxChain.size())                           
                                                         maxChain = x;                           
                                         
                                                         for                                           (Pair pair : maxChain)                           
                                                         cout <<                                           "("                                           << pair.a <<                                           ", "                           
                                                         << pair.b <<                                           ") "                                           ;                           
                             }                           
                                         
                             // Driver Function                           
                             int                                           main()                           
                             {                           
                                                         Pair a[] = {{5, 29}, {39, 40}, {15, 28},                           
                                                         {27, 40}, {50, 90}};                           
                                                         int                                           n =                                           sizeof                                           (a)/                                           sizeof                                           (a[0]);                           
                                         
                                                         vector<Pair> arr(a, a + n);                           
                                         
                                                         maxChainLength(arr);                           
                                         
                                                         return                                           0;                           
                             }                           

Python3

                             # Dynamic Programming solution to construct                           
                             # Maximum Length Chain of Pairs                           
                             class                                           Pair:                           
                                         
                                                         def                                           __init__(                                           self                                           , a, b):                           
                                                         self                                           .a                                           =                                           a                           
                                                         self                                           .b                                           =                                           b                           
                                         
                                                         def                                           __lt__(                                           self                                           , other):                           
                                                         return                                           self                                           .a < other.a                           
                                         
                             def                                           maxChainLength(arr):                           
                                         
                                                         # Function to construct                           
                                                         # Maximum Length Chain of Pairs                           
                                         
                                                         # Sort by start time                           
                                                         arr.sort()                           
                                         
                                                         # L[i] stores maximum length of chain of                           
                                                         # arr[0..i] that ends with arr[i].                           
                                                         L                                           =                                           [[]                                           for                                           x                                           in                                           range                                           (                                           len                                           (arr))]                           
                                         
                                                         # L[0] is equal to arr[0]                           
                                                         L[                                           0                                           ].append(arr[                                           0                                           ])                           
                                         
                                                         # start from index 1                           
                                                         for                                           i                                           in                                           range                                           (                                           1                                           ,                                           len                                           (arr)):                           
                                         
                                                         # for every j less than i                           
                                                         for                                           j                                           in                                           range                                           (i):                           
                                         
                                                         # L[i] = {Max(L[j])} + arr[i]                           
                                                         # where j < i and arr[j].b < arr[i].a                           
                                                         if                                           (arr[j].b < arr[i].a                                           and                           
                                                         len                                           (L[j]) >                                           len                                           (L[i])):                           
                                                         L[i]                                           =                                           L[j]                           
                                         
                                                         L[i].append(arr[i])                           
                                         
                                                         # print max length vector                           
                                                         maxChain                                           =                                           []                           
                                                         for                                           x                                           in                                           L:                           
                                                         if                                           len                                           (x) >                                           len                                           (maxChain):                           
                                                         maxChain                                           =                                           x                           
                                         
                                                         for                                           pair                                           in                                           maxChain:                           
                                                         print                                           (                                           "({a},{b})"                                           .                                           format                                           (a                                           =                                           pair.a,                           
                                                         b                                           =                                           pair.b),                           
                                                         end                                           =                                           " "                                           )                           
                                                         print                                           ()                           
                                         
                             # Driver Code                           
                             if                                           __name__                                           =                                           =                                           "__main__"                                           :                           
                                                         arr                                           =                                           [Pair(                                           5                                           ,                                           29                                           ), Pair(                                           39                                           ,                                           40                                           ),                           
                                                         Pair(                                           15                                           ,                                           28                                           ), Pair(                                           27                                           ,                                           40                                           ),                           
                                                         Pair(                                           50                                           ,                                           90                                           )]                           
                                                         n                                           =                                           len                                           (arr)                           
                                                         maxChainLength(arr)                           
                                         
                             # This code is contributed                           
                             # by vibhu4agarwal                           

输出：

(5, 29) (39, 40) (50, 90)

时间复杂性 上面的动态规划解是O（n） ^2. )其中n是成对数。 辅助空间 程序使用的是O（n） ^2. ).

本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章