Talk:Longest Increasing Subsequence

From Algorithmist

[edit] Error in pseudo code

The article gives the following code:

func lis( a )
   initialize best to an array of 0's.
   for ( i from 1 to n )
      best[i] = 1
      for ( j from 1 to i - 1 )
         if ( a[i] > a[j] )
            best[i] = best[j] + 1
   return max( best )

However, shouldn't best[i] be replaced with best[j] + 1 only when this increases best[i]? That is,

func lis( a )
   initialize best to an array of 0's.
   for ( i from 1 to n )
      best[i] = 1
      for ( j from 1 to i - 1 )
         if ( a[i] > a[j] )
            best[i] = max(best[i], best[j] + 1)
   return max( best )

(the change is in the penultimate line.)

Also, the initialisation of best to an array of 0s seems unnecessary. TMott 18:18, 16 Sep 2005 (EDT)

I believe you are correct, it seems the previous code would report that the LIS has length 2 on this sequence where the top sequence is the sequence we are interested in, and the bottom is the corresponding longest LIS ending at the given element.

3 5 2 6
1 2 1 2

There is an error, we take 2 6 rather than 3 5 6 because the 2 occured later in the sequence than the 5, which is a bad decision. The correct answer is

3 5 2 6
1 2 1 3

--Rrenaud 12:06, 17 Sep 2005 (EDT)

The current version of the page is inconsistent. Note that sometimes the sequence is indexed from 0 to N and sometimes from 1 to N. This has to be fixed. Either use 1 to N or 0 to N-1, so that N represents the count of elements. Indexing from 0 to N can be pretty confusing. --Misof 11:05, 20 Dec 2005 (EST)

This is mostly done, though feel free to help out if I miss any! =) --Larry 15:29, 20 Dec 2005 (EST)