# Longest Increasing Subsequence

The **Longest Increasing Subsequence** problem is to find the longest increasing subsequence of a given sequence. It also reduces to a Graph Theory problem of finding the longest path in a Directed acyclic graph.

## Contents

## Overview[edit]

Formally, the problem is as follows:

Given a sequence , find the largest subset such that for every , .

## Techniques[edit]

### Longest Common Subsequence[edit]

A simple way of finding the longest increasing subsequence is to use the Longest Common Subsequence (Dynamic Programming) algorithm.

- Make a sorted copy of the sequence , denoted as . time.
- Use Longest Common Subsequence on with and . time.

### Dynamic Programming[edit]

There is a straight-forward Dynamic Programming solution in time. Though this is asymptotically equivalent to the Longest Common Subsequence version of the solution, the constant is lower, as there is less overhead.

Let A be our sequence . Define as the length of the longest increasing subsequence of A, subject to the constraint that the subsequence must end on the element . The longest increasing subsequence of A must end on *some* element of A, so that we can find its length by searching for the maximum value of q. All that remains is to find out the values .

But can be found recursively, as follows: consider the set of all such that . If this set is null, then all of the elements that come before are greater than it, which forces . Otherwise, if is not null, then q has some distribution over . By the general contract of q, if we maximize q over , we get the length of the longest increasing subsequence in ; we can append to this sequence, to get that:

If the actual subsequence is desired, it can be found in further steps by moving backward through the q-array, or else by implementing the q-array as a set of stacks, so that the above "+ 1" is accomplished by "pushing" into a copy of the maximum-length stack seen so far.

Some pseudo-code for finding the length of the longest increasing subsequence:

function lis_length( a ) n := a.length q := new Array(n) for k from 0 to n: max := 0; for j from 0 to k, if a[k] > a[j]: if q[j] > max, then set max = q[j]. q[k] := max + 1; max := 0 for i from 0 to n: if q[i] > max, then set max = q[i]. return max;

### Faster Algorithm[edit]

There's also an solution based on some observations. Let be the smallest possible tail out of all increasing subsequences of length using elements .

Observe that, for any particular , . This suggests that if we want the longest subsequence that ends with , we only need to look for a j such that and the length will be .

Notice that in this case, will be equal to , and all will be equal to for .

Furthermore, there is at most one difference between the set and the set , which is caused by this search.

Since is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single .

**Further explain**:--GONG Zhi Tao 11:19, 1 August 2012 (EDT)

We have elements: .

And we have a longest increasing subsequences of them: , for any you could not find a smaller alternative.

Now we have a new element:

What we can do about it:

1. insert it at the back if , where we will have a longer one;

2. make it an alternative for if

Alternative means that we MIGHT get longer ones if using the new element.