HelloKoding

Practical coding guides

Longest Increasing Subsequence

In this article, you will learn to resolve the longest increasing subsequence problems by using a dynamic programming algorithm

A longest increasing subsequence (LIS) is obtained from a sequence, has elements in increasing order and as long as possible

Problem 1: Find length of LIS

  • Given an unsorted array of numbers a
  • Write an algorithm to find the length of the longest increasing subsequence (LIS)
  • The LIS does not necessarily have to be contiguous or unique

Example 1

  • Input: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
  • Output: 6
  • Explanation: The LIS is {0, 2, 6, 9, 11, 15}. It’s not contiguous or unique. Other instances are {0, 2, 6, 9, 13, 15}, {0, 4, 6, 9, 11, 15, {0, 4, 6, 9, 13, 15}

Approach 1.1: Brute force with recursion

  • Using recursion to scan the increasing subsequences of all elements in the given array to find the length of the longest one
  • At each iteration, there are two options: count or not the current element based on its value is greater than the previous element or not, respectively

LISLengthByBruteForce.java

package com.hellokoding.algorithm;

public class LISLengthByBruteForce {
    static int lengthOfLIS(int[] a, int prevIndex, int currIndex) {
        if (currIndex == a.length) {
            return 0;
        }

        int included = 0;
        if (prevIndex < 0 || a[currIndex] > a[prevIndex]) {
            included = 1 + lengthOfLIS(a, currIndex, currIndex+1);
        }

        int excluded = lengthOfLIS(a, prevIndex, currIndex+1);

        return Math.max(included, excluded);
    }

    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
        System.out.println(lengthOfLIS(arr, -1, 0));
    }
}
  • Output
6
  • Time complexity: O(2n) as you have to iterate over all elements in the array and each element has 2 options
  • Space complexity: O(1)

Approach 1.2: Dynamic programming

  • Optimal substructure and overlapping subproblems: say lisi, lisj are length of the LIS at index i and j

    lisi = max(lisi, lisj + 1), ∀0 <= j < i and a[i] > a[j]

  • Use an array cache[n] to cache the length of the LIS at each index corresponding with the given array a[n]
  • Bottom-up filling cache[n] with the base case

    cache[i] = 1, ∀0 <= i < n

  • LIS(a[n]) = max(cache[n])

LISLengthByDPBottomUp.java

package com.hellokoding.algorithm;

import java.util.Arrays;

public class LISLengthByDPBottomUp {
    static int lengthOfLIS(int[] a) {
        if (a.length == 0) {
            return 0;
        }

        int[] cache = new int[a.length];
        Arrays.fill(cache, 1);

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

        return Arrays.stream(cache).max().getAsInt();
    }


    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
        System.out.println(lengthOfLIS(arr));
    }
}
  • Output
6
  • Time complexity: O(n2) as you use 2 for-loop
  • Space complexity: O(n) as you use a cache array which has the same size as the given array

Problem 2: Find LIS

  • Given an unsorted array of numbers a
  • Write an algorithm to find the longest increasing subsequence (LIS)
  • The LIS does not necessarily have to be contiguous or unique

Example 2

  • Input: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
  • Output: [0, 2, 6, 9, 11, 15]
  • Explanation: The LIS is {0, 2, 6, 9, 11, 15}. It’s not contiguous or unique. Other instances are {0, 2, 6, 9, 13, 15}, {0, 4, 6, 9, 11, 15, {0, 4, 6, 9, 13, 15}

Approach 2.1: Dynamic programming

  • Optimal substructure and overlapping subproblems same as the previous approach of problem 1

LISByDPBottomUp.java

package com.hellokoding.algorithm;

import java.util.ArrayList;
import java.util.List;

public class LISByDPBottomUp {
    static List<Integer> findLIS(int[] arr) {
        List<List<Integer>> cache = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            cache.add(new ArrayList<>());
        }

        cache.get(0).add(arr[0]);

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && cache.get(i).size() < cache.get(j).size() + 1) {
                    cache.set(i, new ArrayList<>(cache.get(j)));
                }
            }
            cache.get(i).add(arr[i]);
        }

        List<Integer> longest = cache.get(0);
        for (int i = 0; i < cache.size(); i++) {
            if (longest.size() < cache.get(i).size()) {
                longest = new ArrayList<>(cache.get(i));
            }
        }

        return longest;
    }

    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
        System.out.println(findLIS(arr).toString());
    }
}
  • Output
[0, 2, 6, 9, 11, 15]
  • Time complexity: O(n2) as you use 2 for-loop
  • Space complexity: O(n2) as you use 2D array to cache the increasing subsequences
Follow HelloKoding