Longest Increasing Subsequence

A sequence of numbers a₁, a₂,..., a_n, a sub-sequence is a_i1, a_i2, ... , a_ik where 1 <= i₁ < i₂ < ... < i_k <= n and an increasing sub-sequence is one in which the numbers are getting strictly larger. The task is to find the increasing sub-sequence of greatest length.

Example: The longest increasing sub-sequence of 5, 2, 8, 6, 3, 6, 9, 7 is 2, 3, 6, 9:

Solution: Create a graph of all permissible transitions: establish a node i for each element ai, and add directed edges (i, j) whenever it is possible for a_i and a_j to be consecutive elements in an increasing sub-sequence,that is, whenever i < j and a_i < a_j.

Note that this graph G = (V,E) is a dag, since all edges (i, j) have i < j, and there is a one-to-one correspondence between increasing sub-sequences and paths in this dag. Therefore, our goal is simply to find the longest path in the dag. Here is the algorithm:

Implementation:

int LIS(int arr[], int len)
{
int *L = new int[len];

for(int i = 0; i < len; ++i)
L[i] = 1;

for(int j = 1; j < len; ++j)
{
for(int i = 0; i < j; ++i)
{
if((arr[j] > arr[i]) && (L[j] < L[i] + 1))
L[j] = L[i] + 1;
}
}

int max = 0;
for(int i = 0; i < len; ++i)
{
if(max < L[i])
max = L[i];
}

delete [] L;
return max;
}

Complexity: O(n²)