# Dynamic Programming — Longest Increasing Subsequence

Objec­tive: The longest Increas­ing Sub­se­quence (LIS) prob­lem is to find the length of the longest sub­se­quence in a given array such that all ele­ments of the sub­se­quence are sorted in increas­ing order.

OR

Given a array A[1,2,.…..,n] , cal­cu­late B[1,2.…m] with B[i]<B[i+1] where i=1,2,3,.…,m such that m is maximum.

Exam­ple:

```int[] A = { 1, 12, 7, 0, 23, 11, 52, 31, 61, 69, 70, 2 };

length of LIS is 7 and LIS is {1, 12, 23, 52, 61, 69, 70}.
```

Approach:

Opti­mal Substructure:

```LIS(i) - Length of longest increasing subsequence which includes element A[i] as its last element.

LIS(i) = 1 + Max j=1 to i-1 {LIS(j)} if A[i]>A[j] for 1<j<i
=   1 if no such j exists.```

Over­lap­ping Subproblems:

If we solve using recur­sion for cal­cu­lat­ing the solu­tion for jth index we will be solv­ing the sub­prob­lems again which we had solved ear­lier while solv­ing the solu­tion for (j-1)th index.

```Example:

A[] = {3, 4, 1, 5}

i=1 , LIS(1) = 1

i=2 , LIS(2) = 1+ Max(LIS(1)) = 1 +1 =2 (4>3)

i=3 , LIS(3) = 1 (1>3, 1>4)

i=4 , LIS(4) = 1+ Max(LIS(1),LIS(2), LIS(3))

= 1 + Max(1,2,1) = 3
```

Code:

```Output:
Longest Increasing subsequence: 7
Actual Elements: 1 7 11 31 61 69 70
```

NOTE: To print the Actual elements -

• find the index which con­tains the longest sequence, print that index from main array.
• Start mov­ing back­wards and pick all the indexes which are in sequence (descending).
• If longest sequence for more than one indexes, pick any one.

From our code LIS[] =

#### You may also like...

• John­nyD

Great solu­tion. The end with result and res is amazing.

• Ankit

Here is a code which prints all the subsequences

http://www.edufyme.com/code?id=66f041e16a60928b05a7e228a89c3799

It does that by keep­ing track of length longest increas­ing sub­se­quence at every step and an index to pre­vi­ous ele­ment in the sub­se­quence. If there are mul­ti­ple such val­ues, track them all.

• giraffe0813

Hi, I want to know if the time com­plex­ity is O(n^2) or not? Thanks~~

• tuto­ri­al­hori­zon

Yes it’s O(N^2). I will update the post. Thanks

• Sourabh Goel

if there are more than one longest increas­ing sub­se­quences then how to print all such sub­se­quences. Exam­ples: input[]={10, 22, 9, 33, 21, 50, 41, 60 } Print: 10, 22, 33, 50, 60 and 10, 22, 33, 41, 60

• zsal­abc

pub­lic sta­tic void findSubsequence(int a[]) {

int[] r = new int[a.length];

for (int i = 0; i = 0; i1–) {

for (int i2 = i1+1; i2 < a.length; i2++) {

if (a[i1] < a[i2]) {

r[i1] += r[i2];

break;

}

}

}

int max = 0;

int idx = 0;

System.out.print(“r: ”);

for (int i = 0; i < r.length; i++) {

System.out.print(“ “+r[i]);

if (max < r[i]) {

max = r[i];

idx = i;

}

}

System.out.println();

System.out.println(“Max length: “+max);

System.out.print(“Seqence: “+a[idx]);

for (int i = idx+1; i < a.length; i++) {

if (a[idx] < a[i]) {

System.out.print(“ “+a[i]);

idx = i;

}

}

System.out.println();

}