Geek Answers Handbook

How to print the longest growing subsequence (LIS) from a given array?

I can print the length of the LIS using a regular function and a recursive function. But I want to print this LIS subsequence index in a given array in C ++.

Here is my function to find the length of the LIS:

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

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

here LIS Length=6

I want to print the index of numbers {2 3 4 6 8 9} (its not the sequence of its pointer, which I want to print) the index of the sequence in array[10]

+4
source share
4 answers

After calculating the lis for each index, take the tmp value equal to max, go back to the lis array, and each time you find an element equal to max, add this index to the answer and decrease tmp. This way you get the array of indices in reverse order.

Code example:

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

To print in order, you can use a recursive approach: call: printLIS (lis, lis.length -1, arr, max)

 public static void printLIS(int[] lis, int lisIndex, int[] arr, int max) { if(max == 0) { return; } if(lis[lisIndex] == max) { printLis(lis,lisIndex-1, arr, max-1); System.out.print(arr[lisIndex] + " "); } else { printLis(lis,lisIndex-1, arr, max); } }
+1
source 
 int lis( int *arr, int n ) { int *lis, i, j, max = 0, max_index = 0; int *print = (int*)malloc(sizeof(int)*n); lis = (int*) malloc ( sizeof( int ) * n ); for ( i = 0; i < n; i++ ){ lis[i] = 1; print[i] = -1 } for ( i = 1; i < n; i++ ) for ( j = 0; j < i; j++ ) if ( arr[i] > arr[j] && lis[i] < lis[j] + 1){ lis[i] = lis[j] + 1; print[i] = j; } for ( i = 0; i < n; i++ ){ if ( max < lis[i] ){ max = lis[i]; max_index = i; } } while(max_index >=0){ printf("%d ",lis[max_inc_index]); max_index = print[max_index]; } /* Free memory to avoid memory leak */ free( lis ); return max; }

Use an optional array that tracks indexes that are part of the longest subsequence, and then traverses the array to print all the relevant elements.

0
source

A dynamic array can be declared with its length equal to the maximum length of the increasing sequence. The ANS array will contain the longest ascending sequence.

 int *ans=(int*)malloc(sizeof(int)*max);

A temporary variable is used to store the maximum length index in an array.

  int index; int length; //used to fill array ANS in reverse order. for ( i = 0; i < n; i++ ) { if ( max < lis[i] ) { max = lis[i]; index=i; } } length=max; ans[length-1]=arr[index]; //filling array from the last //last element will be the greatest element length--; while(index>0) { for(i=index-1;i>=0;i--) { if(lis[i]+1==lis[index] && arr[i]<arr[index]) { ans[length-1]=arr[i]; index=i; length--; break; } } } for(i=0;i<max;i++) { printf("%d",ans[i]); }

Here the complexity is O (n), not O (n2), even if it can use two loops, since we change the index value by i whenever a block is entered.

0
source

More articles:


All Articles