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:


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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • JohnnyD

    Great solution. 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 keeping track of length longest increasing subsequence at every step and an index to previous element in the subsequence. If there are multiple such values, track them all.

  • giraffe0813

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

    • tutorialhorizon

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

  • Sourabh Goel

    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

  • zsalabc

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

    }

%d bloggers like this: