# Talk:Longest Increasing Subsequence

## 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)

I find this page difficult to understand, can you provide some examples? It's not easy to understand an algorithm from a pseudo code... I need graphics like those on

Thanks

93.35.61.177 16:57, 11 February 2011 (EST)

## Tail?

The definition of A_{i,j} is unclear. What is a tail?