# Longest Increasing Subsequence

Jump to navigation Jump to search

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.

## Overview

Formally, the problem is as follows:

Given a sequence ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$, find the largest subset such that for every ${\displaystyle i, ${\displaystyle a_{i}.

## Techniques

### Longest Common Subsequence

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

1. Make a sorted copy of the sequence ${\displaystyle A}$, denoted as ${\displaystyle B}$. ${\displaystyle O(n\log(n))}$ time.
2. Use Longest Common Subsequence on with ${\displaystyle A}$ and ${\displaystyle B}$. ${\displaystyle O(n^{2})}$ time.

### Dynamic Programming

There is a straight-forward Dynamic Programming solution in ${\displaystyle O(n^{2})}$ 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 ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$. Define ${\displaystyle q_{k}}$ as the length of the longest increasing subsequence of A, subject to the constraint that the subsequence must end on the element ${\displaystyle a_{k}}$. 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 ${\displaystyle q_{k}}$.

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

${\displaystyle q_{k}=max(q_{j}|j\in S_{k})+1}$

If the actual subsequence is desired, it can be found in ${\displaystyle O(n)}$ 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" ${\displaystyle a_{k}}$ 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

There's also an ${\displaystyle O(n\log {n})}$ solution based on some observations. Let ${\displaystyle A_{i,j}}$ be the smallest possible tail out of all increasing subsequences of length ${\displaystyle j}$ using elements ${\displaystyle a_{1},a_{2},a_{3},\ldots ,a_{i}}$.

Observe that, for any particular ${\displaystyle i}$, ${\displaystyle A_{i,1}. This suggests that if we want the longest subsequence that ends with ${\displaystyle a_{i+1}}$, we only need to look for a j such that ${\displaystyle A_{i,j} and the length will be ${\displaystyle j+1}$.

Notice that in this case, ${\displaystyle A_{i+1,j+1}}$ will be equal to ${\displaystyle a_{i+1}}$, and all ${\displaystyle A_{i+1,k}}$ will be equal to ${\displaystyle A_{i,k}}$ for ${\displaystyle k\neq j+1}$.

Furthermore, there is at most one difference between the set ${\displaystyle A_{i}}$ and the set ${\displaystyle A_{i+1}}$, which is caused by this search.

Since ${\displaystyle A}$ is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$.

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

We have elements: ${\displaystyle a_{1},a_{2},a_{3},\ldots ,a_{i}}$.

And we have a longest increasing subsequences of them: ${\displaystyle A_{i,1}, for any ${\displaystyle A_{i,k}(1<=k<=j)}$ you could not find a smaller alternative.

Now we have a new element: ${\displaystyle a_{i+1}}$

What we can do about it:

1. insert it at the back if ${\displaystyle A_{i,j}, where we will have a longer one;

2. make it an alternative for ${\displaystyle A_{i,k}}$ if ${\displaystyle A_{i,k-1}

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

## Implementation

• C
• C++ (${\displaystyle O(n\log n)}$ algorithm - output sensitive - ${\displaystyle O(n\log k)}$)
• Python (${\displaystyle O(n^{2})}$)