A sequence of numbers a

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:

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;

}

_{1}, a_{2},..., a_{n}, a sub-sequence is a_{i1}, a_{i2}, ... , a_{ik}where 1 <= i_{1}< i_{2}< ... < 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^{2})
## No comments:

## Post a Comment