top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Given an unsorted array, find the max length of subsequence ?

+5 votes
3,003 views

Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

posted Dec 12, 2013 by Gaurav Sharma

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
{2, 3, 5, 8, 9} this is not the correct subsequence. there in i present between 3 and 5.  {2, 3, 1, 5, 8, 9}

1 Answer

0 votes

Temp variable used - MAX, Buffers B1, B2 .

Take 7 and traverse to find the number that is > 7, so here TWO numbers ie 8,9.
Mark this index in temp variable MAX, and save these numbers in another temp buffer B1.

Then take 2 and traverse to find the number that is > 2, so here FIVE numbers ie 3 5 8 9 6 = > B2.
Mark this index in temp variable MAX because because FIVE > TWO , and save these numbers in B1 free B1 or ....

And so on.

Finally print MAX and B1.

answer Dec 12, 2013 by sivanraj
All number of the subarray should be in increment order, but yes your algo with little modification can be used to find the answer.
I did that only...
Similar Questions
+3 votes

Say the given string is ABC

Output should be ABC ACB BAC BCA CBA CAB

+8 votes

Convert the given string into palindrome with minimum number of appends(at end of the given string). O(n) algorithm will be appreciated ??

Input :=> Malayal
Output :=> Malayalam

...