Longest non-decreasing sequence - n log n?

you don't need to store all temp lists at any given point, only the last element will do.

First, let's recall the O (n ² ) solution : you created an array L

that has each element the i

length of the longest non-decreasing subsequence A

ending with the element i

. Here's an example:

A: 2 5 7 3 8 2 9 6 9
L: 1 2 3 2 4 2 5 3 6

      

        
        
        
      

    

Now imagine how to set up an array M

that, at each index, k

stores an element A

that ends up with the longest non-decreasing subsequence of length k

. Here's how M

to look at each step (the dash -

shows the spaces that are not filled)

M (step 0) - - - - - - - - -
M (step 1) 2 - - - - - - - -
M (step 2) 2 5 - - - - - - -
M (step 3) 2 5 7 - - - - - -
M (step 4) 2 3 7 - - - - - -
M (step 5) 2 3 7 8 - - - - -
M (step 6) 2 2 7 8 - - - - -
M (step 7) 2 2 7 8 9 - - - -
M (step 8) 2 2 6 8 9 - - - -
M (step 9) 2 2 6 8 9 9 - - -

      

        
        
        
      

    

Work through the example by hand to understand the mechanics of filling the array M

.

Now comes the key observation: at each step, it is M

ordered in a non-decreasing order . This is intuitive, because otherwise, a larger number can be bound to a longer sequence and move through the array M

.

This allows you to build your own algorithm:

• Save the last position maxPos

M
  
  that was filled
• When you arrive at A[i]
  
  , run a binary search in M[0..maxPos]
  
  for the location where it should be postedA[i]
  
  
• If you hit the middle of the array, replace the old value with min(A[i], oldValue)
  
  
• If an element is greater than or equal to all elements appended to M
  
  , add A[i]
  
  to the end and incrementmaxPos
  
  

It is not hard to see that the above algorithm is O (n * log (n)) since each of its steps n

uses a binary search, which is log (n).