The Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Check LeetCode link for more details and example input & output.

Dynamic Programming Solutions

A Recursive Approach

Comparing with the original problem, it’s easier to solve the longest increasing subsequence which starts at the index i recursively. Let’s call it LIS[i], longest increasing subsequence of nums starting at the index i.

The original problem becomes finding the maximum value among LIS[0], LIS[1], …, LIS[nums.length - 1].

  public int lengthOfLIS(int[] nums) {
      int max = 1;
      for (int i = 0; i < nums.length; i++) {
          max = Math.max(max, lengthOfLISStartAtIndex(nums, i));
      }
      return max;
  }

  int lengthOfLISStartAtIndex(int[] nums, int index) {
      if (index == nums.length - 1) { // the base case
          return 1;
      }

      int result = 1;
      for (int i = index + 1; i < nums.length; i++) {
          // this test guarantees getting an increasing sub-sequence
          if (nums[i] > nums[index]) {
              result = Math.max(result, 1 + lengthOfLISStartAtIndex(nums, i));
          }
      }
      return result;
  }

A Top Down Approach

Improve the recursive solution with caching.

  public int lengthOfLIS(int[] nums) {
      Map<Integer, Integer> cache = new HashMap<>();
      int result = 1;
      for (int i = 0; i < nums.length; i++) {
          result = Math.max(result, lengthOfLIS(nums, i, cache));
      }
      return result;
  }
  
  // length Of LIS starting at `index`
  int lengthOfLIS(int[] nums, int index, Map<Integer, Integer> cache) {
      if (index == nums.length - 1) {
          return 1;
      }
  
      if (cache.get(index) != null) {
          return cache.get(index);
      }
  
      int result = 1;
      for (int i = index + 1; i < nums.length; i++) {
          if (nums[i] > nums[index]) {
              result = Math.max(result, 1 + lengthOfLIS(nums, i, cache));
          }
      }
      cache.put(index, result);
      return result;
  }

A Bottom Up Approach

It’s easy to calculate LIS[i] using a bottom up approach too.

LIS[i] is the maximum of below values.

  • 1 (since at least nums[i] is a candidate of LIS starting at i)
  • 1 + LIS[i+1], if nums[i] < nums[i+1]
  • 1 + LIS[i+2], if nums[i] < nums[i+2]
  • …

Base case is LIS[nums.length - 1] is 1.

Below is a Java solution. 

  public int lengthOfLIS(int[] nums) {
      int[] dp = new int[nums.length];
      Arrays.fill(dp, 1);
      int result = 1;
      for (int i = nums.length - 2; i >= 0; i--) {
          for (int j = i + 1; j < nums.length; j++) {
              if (nums[i] < nums[j]) {
                  dp[i] = Math.max(dp[i], 1 + dp[j]);
              }
          }
          // record the maximum value of LIS[0], LIS[1], ...
          result = Math.max(result, dp[i]);
      }
      return result;
  }

The time complexity is O(n^2).