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

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

Problem 1

  • 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.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


  • 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])


  • 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

  • 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.1

  • 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

  • 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