Longest Increasing Subsequence

Longest Increasing Subsequence Problem statement

Given an array of integers A, find the length of the longest strictly increasing subsequence of A.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: A = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Method 1: Recursive Solution

Let’s consider that LIS(i) is the longest increasing subsequence ending at index i.

Base condition

To determine the base condition of a recursive problem, think about the smallest valid input. In this case, the smallest valid input is i == 0 - when the array has just one element.

LIS(0) = 1 // There is only one element in the array

Recursion

Whenever you write a recursive solution, think about how you can represent the solution to a larger subproblem using the solutions to smaller subproblems.

If we know the length of the Longest Increasing Subsequence LIS(j) for every j < i, then we can easily determine LIS(i) using the following recursion:

LIS(i) = max(LIS(j)) + 1; where a[j] < a[i] and for 0 <= j < i
LIS(i) = 1; if no such j exists

Let’s now write the code for our recursive solution:

import java.util.Scanner;

class LongestIncreasingSubsequenceRecursion {
    private static int longestIncreasingSubsequenceEndingAt(int[] a, int i) {
        if (i == 0) {
            return 1;
        }

        int lisEndingHere = 1;

        for (int j = 0; j < i; j++) {
            if (a[i] > a[j]) {
                lisEndingHere = Math.max(lisEndingHere,
                        longestIncreasingSubsequenceEndingAt(a, j) + 1);
            }
        }

        return lisEndingHere;
    }

    private static int findLengthOfLongestIncreasingSubsequence(int[] a, int n) {
        int lis = 1;

        for (int i = 0; i < n; i++) {
            lis = Math.max(lis, longestIncreasingSubsequenceEndingAt(a, i));
        }

        return lis;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }

        keyboard.close();

        System.out.printf("Length of longest increasing subsequence = %d%n",
                findLengthOfLongestIncreasingSubsequence(a, n - 1));
    }
}

$ javac LongestIncreasingSubsequenceRecursion.java
$ java LongestIncreasingSubsequenceRecursion
8
10 9 2 5 3 7 101 18
Length of longest increasing subsequence = 4

Time Complexity: O(2^n) , Exponential. Learn how to do time complexity analysis for recursive functions

Space Complexity: O(1), no additional space reserved. Only Stack space is used in recursion.

Method 2: Dynamic Programming Top down solution (Memoization)

If you look closely at the recursive structure of the solution, you will notice that we’re doing repetitive calculation for smaller subproblems.

A = [10, 12, 5, 14]

       LIS[3]
    /    |    \
LIS[0] LIS[1] LIS[2]
         |      /  \
       LIS[0] LIS[0] LIS[1]

Let’s look at how we can memoize the solution to subproblems so that we don’t have to compute it again and again.

import java.util.Scanner;

class LongestIncreasingSubsequenceTopDown {
    private static int[] LIS;

    private static int longestIncreasingSubsequenceEndingAt(int[] a, int i) {
        // We have already computed the solution so just return it
        if (LIS[i] != -1) {
            return LIS[i];
        }

        if (i == 0) {
            LIS[i] = 1;
            return LIS[i];
        }

        int lisEndingHere = 1;

        for (int j = 0; j < i; j++) {
            if (a[i] > a[j]) {
                lisEndingHere = Math.max(lisEndingHere,
                        longestIncreasingSubsequenceEndingAt(a, j) + 1);
            }
        }

        LIS[i] = lisEndingHere;
        return LIS[i];
    }

    private static int findLengthOfLongestIncreasingSubsequenceMemoized(int[] a) {
        int n = a.length;
        LIS = new int[n];
        for (int i = 0; i < n; i++) {
            LIS[i] = -1;
        }

        int lis = 1;
        for (int i = 0; i < n; i++) {
            lis = Math.max(lis, longestIncreasingSubsequenceEndingAt(a, i));
        }

        return lis;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }

        keyboard.close();

        System.out.printf("Length of longest increasing subsequence = %d%n",
                findLengthOfLongestIncreasingSubsequenceMemoized(a));
    }
}

$ javac LongestIncreasingSubsequenceTopDown.java
$ java LongestIncreasingSubsequenceTopDown
8
10 9 2 5 3 7 101 18
Length of longest increasing subsequence = 4

Time Complexity: O(n^2). We solve the problem for every n. Every subproblem has one for loop which takes O(n).

Space Complexity: O(n), for storing the memoized solutions.

Method 3: Dynamic Programming Bottom up solution

Let’s now try to write a bottom up dynamic programming solution. In bottom up solution, we try to compute the answers to smaller problems first before computing the answers to the larger subproblems. So we first calculate LIS[0] followed by LIS[1], LIS[2] and so on…

class LongestIncreasingSubsequenceBottomUp {

	private static int findLengthOfLongestIncreasingSubsequence(int[] a) {
		int n = a.length;
		int[] LIS = new int[n];
		int longestIncreasingSubsequence = Integer.MIN_VALUE;

		for (int i = 0; i < n; i++) {
			LIS[i] = 1;
			for (int j = 0; j < i; j++) {
				if (a[i] > a[j] && LIS[i] < LIS[j] + 1) {
					LIS[i] = LIS[j] + 1;
				}
			}
			if (longestIncreasingSubsequence < LIS[i]) {
				longestIncreasingSubsequence = LIS[i];
			}
		}

		return longestIncreasingSubsequence;
	}

	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);

		int n = keyboard.nextInt();
		int[] a = new int[n];

		for (int i = 0; i < n; i++) {
			a[i] = keyboard.nextInt();
		}

		keyboard.close();

		System.out.printf("Length of longest increasing subsequence = %d%n",
				findLengthOfLongestIncreasingSubsequence(a));
	}
}

$ javac LongestIncreasingSubsequenceBottomUp.java
$ java LongestIncreasingSubsequenceBottomUp
8
10 9 2 5 3 7 101 18
Length of longest increasing subsequence = 4

Time and space complexity is same as the memoized solution.

Time Complexity: O(n^2).

Space Complexity: O(n).

Dynamic Programming