Longest Increasing Subsequence

Input

nums: the integer sequence

Output

the length of longest increasing subsequence

Examples

Example 1:

Input:

1nums = [50, 3, 10, 7, 40, 80]

Output: 4

Explanation:

The longest increasing subsequence is [3, 7, 40, 80] which has length 4.

Example 2:

Input:

1nums = [1, 2, 4, 3]

Output: 3

Explanation:

Both [1, 2, 4] and [1, 2, 3] are longest increasing subsequences which have length 3.

Try it yourself

Solution

Brute Force

A brute force method traverses through all 2^N possible subsequences, which is essentially generating all subsets. There are 2^N since, for every element, we either include it or exclude it. Then, for every subsequence, we check if it is increasing in O(N) time. Out of all increasing subsequences, we'll find the longest one and return its length.

The final time complexity is going to be O(N * 2^N) and the space complexity is also O(N * 2^N) since we must generate and store all O(2^N) subsets each of length O(N). The following is the implementation of this idea:

1// function to generate all 2^N subsets and store them into the list subsets
2void dfs(int i, vector<int> cur, vector<int> nums, vector<vector<int>>& res) {
3  if (i == nums.size()) return;
4  cur.emplace_back(nums[i]);
5  vector<int> list(cur);
6  res.emplace_back(list);
7  dfs(i + 1, cur, nums, res);
8  cur.pop_back();
9  dfs(i + 1, cur, nums, res);
10}
11
12vector<vector<int>> generate_subsets(vector<int> nums) {
13  vector<vector<int>> res;
14  vector<int> empty;
15  res.emplace_back(empty);
16  dfs(0, {}, nums, res);
17  return res;
18}
19
20// function to check if list nums is strictly increasing
21bool is_increasing(vector<int> &nums) {
22  int N = (int) nums.size();
23  for (int i = 1; i < N; ++i) {
24    if (nums[i - 1] >= nums[i]) {
25      return false;
26    }
27  }
28  return true;
29}
30
31// function to get all subsequence and find longest increasing subsequence
32int longest_sub_len(vector<int> &nums) {
33  vector<vector<int>> subsets = generate_subsets(nums);
34  int mx_len = 0;
35  for (auto &subset: subsets) {
36    if (is_increasing(subset)) {
37      mx_len = max(mx_len, (int) subset.size());
38    }
39  }
40  return mx_len;
41}
42

1// function to generate all 2^N subsets and store them into the list subsets
2public static void dfs(int i, List<Integer> cur, List<Integer> nums, List<List<Integer>> res) {
3  if (i == nums.size()) return;
4  cur.add(nums.get(i));
5  res.add(new ArrayList<>(cur));
6  dfs(i + 1, cur, nums, res);
7  cur.remove(cur.size() - 1);
8  dfs(i + 1, cur, nums, res);
9}
10
11public static List<List<Integer>> generateSubsets(List<Integer> nums) {
12  List<List<Integer>> res = new ArrayList<>();
13  res.add(new ArrayList<>());
14  dfs(0, new ArrayList<>(), nums, res);
15  return res;
16}
17
18// function to check if list nums is strictly increasing
19public static boolean isIncreasing(List<Integer> nums) {
20  int N = nums.size();
21  for (int i = 1; i < N; ++i) {
22    if (nums.get(i - 1) >= nums.get(i)) {
23      return false;
24    }
25  }
26  return true;
27}
28
29// function to get all subsequence and find longest increasing subsequence
30public static int longestSubLen(List<Integer> nums) {
31  List<List<Integer>> subsets = generateSubsets(nums);
32  int mxLen = 0;
33  for (List<Integer> subset : subsets) {
34    if (isIncreasing(subset)) {
35      mxLen = Math.max(mxLen, subset.size());
36    }
37  }
38  return mxLen;
39}
40

1// function to generate all 2^N subsets and store them into the list subsets
2function generateSubsets(nums) {
3  const res = [[]];
4  function dfs(i, cur) {
5      if (i == nums.length) {
6          return;
7      }
8      cur.push(nums[i]);
9      res.push([...cur]);
10      dfs(i + 1, cur);
11      cur.pop();
12      dfs(i + 1, cur);
13  }
14  dfs(0, []);
15  return res;
16}
17
18// function to check if list nums is strictly increasing
19function isIncreasing(nums) {
20  let N = nums.length;
21  for (let i = 1; i < N; ++i) {
22    if (nums[i - 1] >= nums[i]) {
23      return false;
24    }
25  }
26  return true;
27}
28
29// function to get all subsequence and find longest increasing subsequence
30function longestSubLen(nums) {
31  let subsets = generateSubsets(nums);
32  let mxLen = 0;
33  for (const subset of subsets) {
34    if (isIncreasing(subset)) {
35      mxLen = Math.max(mxLen, subset.length);
36    }
37  }
38  return mxLen;
39}
40

1# function to generate all 2^N subsets and store them into the list subsets
2def generate_subsets(nums):
3    n = len(nums)
4    res = [[]]
5    def dfs(i, cur):
6        if i == n:
7            return
8        res.append(cur + [nums[i]])
9        dfs(i + 1, cur + [nums[i]])
10        dfs(i + 1, cur)
11    dfs(0, [])
12    return res
13
14# function to check if list nums is strictly increasing
15def is_increasing(nums):
16  n = len(nums)
17  for i in range(1, n):
18    if nums[i - 1] >= nums[i]:
19      return False
20  return True
21
22# function to get all subsequence and find longest increasing subsequence
23def longest_sub_len(nums):
24  subsets = generate_subsets(nums)
25  mx_len = 0
26  for subset in subsets:
27    if is_increasing(subset):
28      mx_len = max(mx_len, len(subset))
29  return mx_len
30

DFS + Memoization

The keywords "longest" and "sequence" are good indicators of dynamic programming.

Let's try thinking about a dp solution. First, what is the overall problem that we want to solve? It's "what is the LIS of a sequence of N numbers?"

What is the dp state? Typically when you think of a dp solution for sequences, we consider a prefix of the original sequence. In this case the state is: considering the first i numbers (nums[1], nums[2], ... nums[i]), what is the longest increasing subsequence that contains nums[i]?

Next, the transition. If we want to build an LIS that ends with nums[i], then we need to find a previously exisiting LIS that ends with a number less than nums[i]. In order words, find the largest existing LIS (j < i) where nums[j] < nums[i], and simply append nums[i] to that LIS!

Here are figures of this idea:

A simple base case would be if i = 0 then return 0 since if we don't have any elements the longest increasing subsequence is of length 0.

Here's a summary of the dp relationship:

state: f(i) is the longest increasing subsequence that ends/contains nums[i].
base case: f(0) = 0: an empty list has an LIS of length 0.
transition: f(i) = max(f(j) + 1) for j = 0 ... i-1 as long as nums[j] < nums[i] (extend a pre-existing LIS)

As usual with problems with recursive relations, we store a memo table to store answers that may be reused to stop unnecessary recomputations.

Here's the implementation of this idea:

1int f(int i, vector<int> &nums, vector<int> &memo, int &lis) { // pass lis by reference to act like a global variable
2  if (i == 0) {
3    return 0;
4  }
5  if (memo[i] != 0) { // if already computed, use said answer
6    return memo[i];
7  }
8  int len = f(0, nums, memo, lis) + 1; // begin with starting a new LIS
9  int ni = nums[i - 1];
10
11  for (int j = 1; j < i; j++) { // try building upon a pre-existing LIS
12    int nj = nums[j - 1];
13    int f_of_j = f(j, nums, memo, lis); // compute f(j), otherwise if nums[i] < nums[j] then f(j) will never be computed
14    if (nj < ni) {
15      len = max(len, f_of_j + 1);
16    }
17  }
18  // LIS can end anywhere in the sequence due to the definition of our state, so update each time
19  lis = max(lis, len);
20
21  return memo[i] = len;
22}
23
24int longest_sub_len(vector<int> &nums) {
25  int n = (int) nums.size();
26  vector<int> memo(n + 1, 0);
27  int lis = 0;
28  f(n, nums, memo, lis);
29  return lis;
30}
31

1public static int lis = 0; // global variable to store answer
2
3public static int f(int i, List<Integer> nums, int[] memo) {
4  if (i == 0) {
5    return 0;
6  }
7  if (memo[i] != 0) { // if already computed, use said answer
8    return memo[i];
9  }
10  int len = f(0, nums, memo) + 1; // begin with starting a new LIS
11  int ni = nums.get(i - 1);
12
13  for (int j = 1; j < i; j++) { // try building upon a pre-existing LIS
14    int nj = nums.get(j - 1);
15    int f_of_j = f(j, nums, memo); // compute f(j), otherwise if nums[i] < nums[j] then f(j) will never be computed
16    if (nj < ni) {
17      len = Math.max(len, f_of_j + 1);
18    }
19  }
20  // LIS can end anywhere in the sequence due to the definition of our state, so update each time
21  lis = Math.max(lis, len);
22
23  return memo[i] = len;
24}
25public static int longestSubLen(List<Integer> nums) {
26  int n = nums.size();
27  int[] memo = new int[n + 1];
28  Arrays.fill(memo, 0);
29  f(n, nums, memo);
30  return lis;
31}
32

1let lis = 0; // global variable to store answer
2
3function f(i, nums, memo) {
4  if (i === 0) {
5    return 0;
6  }
7  if (memo[i] !== 0) { // if already computed, use said answer
8    return memo[i];
9  }
10  let len = f(0, nums, memo) + 1; // begin with starting a new LIS
11  let ni = nums[i - 1];
12
13  for (let j = 1; j < i; j++) { // try building upon a pre-existing LIS
14    let nj = nums[j - 1];
15    let f_of_j = f(j, nums, memo); // compute f(j), otherwise it may never be computed
16    if (nj < ni) {
17      len = Math.max(len, f_of_j + 1);
18    }
19  }
20  // LIS can end anywhere in the sequence due to the definition of our state, so update each time
21  lis = Math.max(lis, len);
22
23  return memo[i] = len;
24}
25
26function longestSubLen(nums) {
27  let n = nums.length;
28  let memo = new Array(n + 1).fill(0);
29  f(n, nums, memo);
30  return lis;
31}
32

1global lis # global variable to store answer
2
3def f(i, nums, memo):
4  global lis
5
6  if i == 0:
7    return 0
8
9  if memo[i] != 0: # if already computed, use said answer
10    return memo[i]
11
12  len = f(0, nums, memo) + 1 # begin with starting a new LIS
13  ni = nums[i - 1]
14  for j in range(1, i): # try building upon a pre-existing LIS
15    nj = nums[j - 1]
16    f_of_j = f(j, nums, memo) # compute f(j), otherwise if nums[i] < nums[j] then f(j) will never be computed
17    if nj < ni:
18      len = max(len, f_of_j + 1)
19
20  # LIS can end anywhere in the sequence due to the definition of our state, so update each time
21  lis = max(lis, len)
22
23  memo[i] = len
24  return len
25
26def longest_sub_len(nums):
27  global lis
28  lis = 0
29  n = len(nums)
30  memo = [0] * (n + 1)
31  f(n, nums, memo)
32  return lis
33

The runtime of this solution is O(n^2) where n is the number of elements in nums since there are O(n) states and each state takes O(n) to compute. The space complexity is O(n) due to the use of the memo array.

Bottom-up DP

This can even be done iteratively. This is similar to the recursive version, except instead of going from top-down, we build our solution from the bottom-up. We can do this because a larger solution f(n) will depend on smaller solutions f(0)...f(n-1).

Here is a figure of the idea:

Here is the implementation of the idea:

1int longest_sub_len(vector<int> &nums) {
2  int N = (int) nums.size();
3  vector<int> dp(N + 1, 0);
4
5  dp[0] = 0; // base case: no elements has an LIS of length 0
6  int len = 0;
7  for (int i = 1; i <= N; ++i) {
8    int ni = nums[i - 1];
9    dp[i] = dp[0] + 1; // first we try starting a new sequence
10
11    for (int j = 1; j < i; ++j) { // then try extending an existing LIS from indices less than i
12      int nj = nums[j - 1];
13      if (nj < ni) {
14        dp[i] = max(dp[i], dp[j] + 1);
15      }
16    }
17
18    len = max(len, dp[i]);
19  }
20  return len;
21}
22

1public static int longestSubLen(List<Integer> nums) {
2  int N = nums.size();
3  int[] dp = new int[N + 1];
4  
5  dp[0] = 0; // base case: no elements has an LIS of length 0
6  int len = 0;
7  for (int i = 1; i <= N; ++i) {
8    int ni = nums.get(i - 1);
9    dp[i] = dp[0] + 1; // first we try starting a new sequence
10
11    for (int j = 1; j < i; ++j) { // then try extending an existing LIS from indices less than i
12      int nj = nums.get(j - 1);
13      if (nj < ni) {
14        dp[i] = Math.max(dp[i], dp[j] + 1);
15      }
16    }
17
18    len = Math.max(len, dp[i]);
19  }
20  return len;
21}
22

1function longestSubLen(nums) {
2  let N = nums.length;
3  let dp = new Array(N + 1).fill(0);
4
5  dp[0] = 0; // base case: no elements has an LIS of length 0
6  let len = 0;
7  for (let i = 1; i <= N; ++i) {
8    let ni = nums[i - 1];
9    dp[i] = dp[0] + 1; // first we try starting a new sequence
10
11    for (let j = 1; j < i; ++j) { // then try extending an existing LIS from indices less than i
12      let nj = nums[j - 1];
13      if (nj < ni) {
14        dp[i] = Math.max(dp[i], dp[j] + 1);
15      }
16    }
17
18    len = Math.max(len, dp[i]);
19  }
20  return len;
21}
22

1def longest_sub_len(nums):
2  n = len(nums)
3  dp = [0] * (n + 1)
4  
5  dp[0] = 0 # base case: no elements has an LIS of length 0
6  max_len = 0
7  for i in range(1, n + 1):
8    ni = nums[i - 1]
9    dp[i] = dp[0] + 1 # first we try starting a new sequence
10
11    for j in range(1, i): # then try extending an existing LIS from indices less than i
12      nj = nums[j - 1]
13      if nj < ni:
14        dp[i] = max(dp[i], dp[j] + 1)
15    
16    max_len = max(max_len, dp[i])
17  
18  return max_len
19

The runtime for this solution is O(n^2) since there are O(n) states and each state takes O(n) to compute. The space complexity is O(n) due to the use of the dp array of length O(n).

`O(n log n)` with DP and binary search

We're going to first construct a different DP solution that still runs in O(n^2) time and later see how we can improve it to O(n log n).

Let dp[i] be the last element for an LIS of length i. If there are multiple elements, then choose the smallest one.

We will assume that dp[0] = -∞ and all other elements dp[i] = ∞. Then, process the elements in nums one by one while maintaining the state we state above and keep dp[i] updated. Our answer will be the largest i such that dp(i) != ∞.

Here's the implementation and an accompanying figure of this idea:

1int longest_sub_len(vector<int> &nums) {
2  int n = (int) nums.size();
3  const int INFINITY = numeric_limits<int>::max();
4  vector<int> dp(n + 1, INFINITY);
5  dp[0] = -INFINITY;
6
7  for (int i = 0; i < n; i++) {
8    for (int j = 1; j <= n; j++) {
9      if (dp[j-1] < nums[i] && nums[i] < dp[j]) {
10        dp[j] = nums[i];
11      }
12    }
13  }
14
15  int ans = 0;
16  for (int i = 0; i <= n; i++) {
17    if (dp[i] < INFINITY) {
18      ans = i;
19    }
20  }
21  return ans;
22}
23

1public static int longestSubLen(List<Integer> nums) {
2  int n = nums.size();
3  final int INFINITY = Integer.MAX_VALUE;
4  int[] dp = new int[n + 1];
5  Arrays.fill(dp, INFINITY);
6  dp[0] = -INFINITY;
7
8  for (int i = 0; i < n; i++) {
9    for (int j = 1; j <= n; j++) {
10      if (dp[j-1] < nums.get(i) && nums.get(i) < dp[j]) {
11        dp[j] = nums.get(i);
12      }
13    }
14  }
15  
16  int ans = 0;
17  for (int i = 0; i <= n; i++) {
18    if (dp[i] < INFINITY) {
19      ans = i;
20    }
21  }
22  return ans;
23}
24

1function longestSubLen(nums) {
2  let n = nums.length;
3  const INFINITY = Number.MAX_VALUE;
4  let dp = new Array(n + 1).fill(INFINITY);
5  dp[0] = -INFINITY;
6
7  for (let i = 0; i < n; i++) {
8    for (let j = 1; j <= n; j++) {
9      if (dp[j-1] < nums[i] && nums[i] < dp[j]) {
10        dp[j] = nums[i];
11      }
12    }
13  }
14
15  let ans = 0;
16  for (let i = 0; i <= n; i++) {
17    if (dp[i] < INFINITY) {
18      ans = i;
19    }
20  }
21  return ans;
22}
23

1def longest_sub_len(nums):
2  n = len(nums)
3  dp = [inf] * (n + 1)
4  dp[0] = -inf
5
6  for i in range(0, n):
7    for j in range(1, n + 1):
8      if dp[j-1] < nums[i] and nums[i] < dp[j]:
9        dp[j] = nums[i]
10  
11  ans = 0
12  for i in range(0, n + 1):
13    if dp[i] < inf:
14      ans = i
15  return ans
16

If we look at the diagram above we see that dp array will always be sorted: dp[i - 1] <= dp[i] for all i = 1...n. Also, for every nums[i], we only update the dp array once.

This means, our goal for every nums[i] is to find the first number in dp strictly greater than nums[i]. This can be done with binary search in O(log n) time. Thus, the final runtime is O(n log n).

1from math import inf
2from typing import List
3
4def upper_bound(dp, target):
5  n = len(dp)
6  lo, hi = 0, n
7  while lo < hi: