Looking for a hint (not the answer) on how to return the longest acsending non contiguous substring when I already have the length

Question

My code currently returns the length of the largest substring:

for(int i = 1; i<=l-1;i++)
{
   counter = 1;

   for(int j = 0; j<i;j++)
   {
      if(seq[j]<seq[j+1])
      {
         count[j] = counter++;    
      }
   }
}
     for(int i = 0;i<l-1;i++)
     {
        if(largest < count[i+1])
        {
           largest = count[i+1];
        }

     }

assuming seq is the numbers in the sequence. So if the sequence is: 5;3;4;8;6;7, it prints out 4. However, I would like it to also print out 3;4;6;7 which is the longest subsisting in ascending order.

I am trying to get the length of the largest sub sequence itself and the actual sequence, but I already have length.. My instinct is to store each number in the array, while it is working out the count, with the count. So returning the longest count, can also return the array attatched to it. I think this can be done with hashtables, but I'm not sure how to use those.

I am just looking for a hint, not the answer.

Thanks

Answer 1

You need to implement a dynamic programming algorithm for the longest ascending subsequence. The idea is to store a pair of values for each position i:

• The length of the longest ascending subsequence that ends at position i
• The index of the item preceding the current one in such ascending subsequence, or -1 if all prior numbers are greater than or equal to the current one.

You can easily build both these arrays by setting the first pair to {Length=1, Prior=-1}, walking the array in ascending order, and looking for the "best" predecessor for the current item at index i. The predecessor must fit these two conditions:

• It must have lower index and be smaller than the item at i, and
• It must end an ascending subsequence of length greater than the one that you have found so far.

Here is how the data would look for your sequence:

Index:        0  1  2  3  4  5
Value:        5  3  4  8  6  7
------------  ----------------
Length:       1  1  2  3  3  4
Predecessor: -1 -1  1  2  2  4

Once you finish the run, find the max value among lengths array, and chain it back to the beginning using the predecessor's indexes until you hit -1.