Dynamic Programming – Longest Increasing Subsequence

Objective: The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence in a given array such that all elements of the subsequence are sorted in increasing order.

OR

Given a array A[1,2,……,n] , calculate B[1,2….m] with B[i]Example:

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:

Optimal 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

Overlapping Subproblems:

If we solve using recursion for calculating the solution for jth index we will be solving the subproblems again which we had solved earlier while solving the solution 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:

public class LongestIncreasingSubsequence {
public void findSubsequence(int[] arrA) {
int[] LIS = new int[arrA.length];
for (int i = 0; i < arrA.length; i++) {
int max = 1;
for (int j = 0; j < i; j++) {
// check if previous elements > current element
if (arrA[i] > arrA[j]) {
// update the max from the previous entries
if (max == 1 || max < LIS[j] + 1) {
max = 1 + LIS[j];
}
}
}
if (max == 1) {
// means none of the previous element has smaller than arrA[i]
max = 1;
}
LIS[i] = max;
}
// find the max in the LIS[]
int result = 1;
int index = 1;
for (int i = 0; i < LIS.length; i++) {
if (result < LIS[i]) {
result = LIS[i];
index = i;
}
}
// Print the result
// Start moving backwards from the end and
String path = arrA[index] + " ";
int res = result1;
for (int i = index1; i >= 0; i) {
if(LIS[i]==res){
path = arrA[i] + " " + path;
res;
}
}
System.out.println("Longest Increasing subsequence: " + result);
System.out.println("Actual Elements: " + path);
}
public static void main(String[] args) {
int[] A = { 1, 12, 7, 0, 23, 11, 52, 31, 61, 69, 70, 2 };
LongestIncreasingSubsequence i = new LongestIncreasingSubsequence();
i.findSubsequence(A);
}
}

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

NOTE: To print the Actual elements –

  • find the index which contains the longest sequence, print that index from main array.
  • Start moving backwards 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[] =

Longest Increasing Subsequence - track the result

6 thoughts on “Dynamic Programming – Longest Increasing Subsequence”

  1. if there are more than one longest increasing subsequences then how to print all such subsequences. Examples: input[]={10, 22, 9, 33, 21, 50, 41, 60 } Print: 10, 22, 33, 50, 60 and 10, 22, 33, 41, 60

    Reply
  2. How about this solution?

    public static 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();

    }

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.