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 ; }