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)`.