最长递增子序列的C/C++程序-yiteyi-C++库

最长递增子序列（LIS）问题是求给定序列的最长子序列的长度，使子序列的所有元素按递增顺序排序。例如，{10,22,9,33,21,50,41,60,80}的LIS的长度是6，LIS的长度是{10,22,33,50,60,80}。

null

longest-increasing-subsequence

更多示例：

Input  : arr[] = {3, 10, 2, 1, 20}Output : Length of LIS = 3The longest increasing subsequence is 3, 10, 20Input  : arr[] = {3, 2}Output : Length of LIS = 1The longest increasing subsequences are {3} and {2}Input : arr[] = {50, 3, 10, 7, 40, 80}Output : Length of LIS = 4The longest increasing subsequence is {3, 7, 40, 80}

最佳子结构： 设arr[0..n-1]为输入数组，L（i）为以索引i结尾的LIS的长度，以使arr[i]为LIS的最后一个元素。然后，L（i）可以递归地写为： L（i）=1+max（L（j）），其中0 L（i）=1，如果不存在这样的j。为了找到给定数组的LIS，我们需要返回max（L（i）），其中0 因此，我们认为LIS问题满足最优子结构性质，因为主要问题可以用子问题的解来解决。

下面是LIS问题的简单递归实现。它遵循上面讨论的递归结构。

C++

                         /* A Naive C++ recursive implementation of LIS problem */                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         /* To make use of recursive calls, this function must return                       
                                                 two things:                       
                                                 1) Length of LIS ending with element arr[n-1]. We use                       
                                                 max_ending_here for this purpose                       
                                                 2) Overall maximum as the LIS may end with an element                       
                                                 before arr[n-1] max_ref is used this purpose.                       
                                                 The value of LIS of full array of size n is stored in                       
                                                 *max_ref which is our final result */                       
                         int                                     _lis(                                     int                                     arr[],                                     int                                     n,                                     int                                     * max_ref)                       
                         {                       
                                   
                                                 /* Base case */                       
                                                 if                                     (n == 1)                       
                                                 return                                     1;                       
           
                                                 // 'max_ending_here' is length of LIS ending with arr[n-1]                       
                                                 int                                     res, max_ending_here = 1;                       
           
                                                 /* Recursively get all LIS ending with arr[0], arr[1] ...                       
                                                 arr[n-2]. If   arr[i-1] is smaller than arr[n-1], and                       
                                                 max ending with arr[n-1] needs to be updated, then                       
                                                 update it */                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 res = _lis(arr, i, max_ref);                       
                                                 if                                     (arr[i - 1] < arr[n - 1] &&                       
                                                 res + 1 > max_ending_here)                       
                                                 max_ending_here = res + 1;                       
                                                 }                       
           
                                                 // Compare max_ending_here with the overall max. And                       
                                                 // update the overall max if needed                       
                                                 if                                     (*max_ref < max_ending_here)                       
                                                 *max_ref = max_ending_here;                       
           
                                                 // Return length of LIS ending with arr[n-1]                       
                                                 return                                     max_ending_here;                       
                         }                       
           
                         // The wrapper function for _lis()                       
                         int                                     lis(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                   
                                                 // The max variable holds the result                       
                                                 int                                     max = 1;                       
           
                                                 // The function _lis() stores its result in max                       
                                                 _lis(arr, n, &max);                       
           
                                                 // returns max                       
                                                 return                                     max;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                   
                                                 cout <<                                     "Length of lis is "                                     << lis(arr, n) <<                                     ""                                     ;                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by Shubhamsingh10                       

C

                         /* A Naive C recursive implementation of LIS problem */                       
                         #include <stdio.h>                       
                         #include <stdlib.h>                       
           
                         /* To make use of recursive calls, this function must return                       
                                                 two things:                       
                                                 1) Length of LIS ending with element arr[n-1]. We use                       
                                                 max_ending_here for this purpose                       
                                                 2) Overall maximum as the LIS may end with an element                       
                                                 before arr[n-1] max_ref is used this purpose.                       
                                                 The value of LIS of full array of size n is stored in                       
                                                 *max_ref which is our final result */                       
                         int                                     _lis(                                     int                                     arr[],                                     int                                     n,                                     int                                     * max_ref)                       
                         {                       
                                                 /* Base case */                       
                                                 if                                     (n == 1)                       
                                                 return                                     1;                       
           
                                                 // 'max_ending_here' is length of LIS ending with arr[n-1]                       
                                                 int                                     res, max_ending_here = 1;                       
           
                                                 /* Recursively get all LIS ending with arr[0], arr[1] ...                       
                                                 arr[n-2]. If   arr[i-1] is smaller than arr[n-1], and                       
                                                 max ending with arr[n-1] needs to be updated, then                       
                                                 update it */                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++) {                       
                                                 res = _lis(arr, i, max_ref);                       
                                                 if                                     (arr[i - 1] < arr[n - 1] && res + 1 > max_ending_here)                       
                                                 max_ending_here = res + 1;                       
                                                 }                       
           
                                                 // Compare max_ending_here with the overall max. And                       
                                                 // update the overall max if needed                       
                                                 if                                     (*max_ref < max_ending_here)                       
                                                 *max_ref = max_ending_here;                       
           
                                                 // Return length of LIS ending with arr[n-1]                       
                                                 return                                     max_ending_here;                       
                         }                       
           
                         // The wrapper function for _lis()                       
                         int                                     lis(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // The max variable holds the result                       
                                                 int                                     max = 1;                       
           
                                                 // The function _lis() stores its result in max                       
                                                 _lis(arr, n, &max);                       
           
                                                 // returns max                       
                                                 return                                     max;                       
                         }                       
           
                         /* Driver program to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 printf                                     (                                     "Length of lis is %d"                                     ,                       
                                                 lis(arr, n));                       
                                                 return                                     0;                       
                         }                       

输出：

Length of lis is 5

请参阅完整的文章动态规划|集3（最长递增子序列）更多细节！

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

THE END

技术文章