Longest Increasing Subsequence | DP | A Naive C ++ recursive implementation of LIS problem ; stores the LIS ; To make use of recursive calls , thisfunction must return two things : 1 ) Length of LIS ending with element arr [ n - 1 ] . We use max_ending_here for this purpose2 ) 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 ; Base case ; ' max _ ending _ here ' is length of LIS ending with arr [ n - 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 ; Compare max_ending_here with the overall max . And update the overall max if needed ; Return length of LIS ending with arr [ n - 1 ] ; The wrapper function for _lis ( ) ; The max variable holds the result ; The function _lis ( ) stores its result in max ; returns max ; Driver program to test above function
#include <iostream> NEW_LINE using namespace std ; static int max_ref ; int _lis ( int arr [ ] , int n , int * max_ref ) { if ( n == 1 ) return 1 ; int res , max_ending_here = 1 ; 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 ; } if ( * max_ref < max_ending_here ) * max_ref = max_ending_here ; return max_ending_here ; } int lis ( int arr [ ] , int n ) { int max = 1 ; _lis ( arr , n , & max ) ; return max ; } 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 ; }