Thursday, July 9, 2015

Longest Increasing Subsequence

A sequence of numbers a1, a2,..., an, a sub-sequence is ai1, ai2, ... , aik where 1 <= i1 < i2 < ... < ik <= 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 ai and aj to be consecutive elements in an increasing sub-sequence,that is, whenever i < j and ai < aj.


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(n2)

No comments:

Post a Comment