c++ - How to print Longest Increasing Subsequence(LIS) from a given array? -

c++ - How to print Longest Increasing Subsequence(LIS) from a given array? -

i can print length of lis normal function , recursive function. want print index of lis subsequence in given array in c++.

here function find length of lis :

int lis( int *arr, int n ) { int *lis, i, j, max = 0; lis = (int*) malloc ( sizeof( int ) * n ); ( = 0; < n; i++ ) lis[i] = 1; ( = 1; < n; i++ ) ( j = 0; j < i; j++ ) if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; ( = 0; < n; i++ ) if ( max < lis[i] ) max = lis[i]; /* free memory avoid memory leak */ free( lis ); homecoming max; }

here array[10]={7 6 2 3 4 1 8 5 9 10}

here lis length=6

i wanna print index of numbers {2 3 4 6 8 9} ( not sequence arrray index , wanna print ) index of sequence in array[10]

after calculating lis each index, take tmp value equal max, go backwards on lis array, , every time find element equal max, add together index reply , decrement tmp. hereby you'll indexes array in reversed order.

example code:

int tmp = max; std::vector<int> indexes; for( = n - 1; >= 0; --i ) if( lis[ ] == tmp ) { indexes.push_back( ); --tmp; } std::reverse( indexes.begin(), indexes.end());

c++ algorithm