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}
421// 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}
401// 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}
401# 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
30DFS + 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/containsnums[i]. - base case:
f(0) = 0: an empty list has an LIS of length 0. - transition:
f(i) = max(f(j) + 1)forj = 0 ... i-1as long asnums[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}
311public 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}
321let 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}
321global 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
33The 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}
221public 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}
221function 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}
221def 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
19The 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}
231public 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}
241function 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}
231def 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
16If 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:
8 mid = (lo + hi) // 2
9 if dp[mid] > target:
10 hi = mid
11 else:
12 lo = mid + 1
13 return lo
14
15def longest_sub_len(nums):
16 n = len(nums)
17 dp = [inf] * (n + 1)
18 dp[0] = -inf
19
20 for i in range(0, n):
21 j = upper_bound(dp, nums[i])
22 if dp[j-1] < nums[i] and nums[i] < dp[j]:
23 dp[j] = nums[i]
24
25 ans = 0
26 for i in range(0, n + 1):
27 if dp[i] < inf:
28 ans = i
29 return ans
30
31if __name__ == '__main__':
32 nums = [int(x) for x in input().split()]
33 res = longest_sub_len(nums)
34 print(res)
351import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int upperBound(int[] dp, int target) {
8 int n = dp.length;
9 int lo = 0, hi = n;
10 while (lo < hi) {
11 int mid = lo + (hi - lo) / 2;
12 if (dp[mid] > target) {
13 hi = mid;
14 } else {
15 lo = mid + 1;
16 }
17 }
18 return lo;
19 }
20 public static int longestSubLen(List<Integer> nums) {
21 int n = nums.size();
22 final int INFINITY = Integer.MAX_VALUE;
23 int[] dp = new int[n + 1];
24 Arrays.fill(dp, INFINITY);
25 dp[0] = -INFINITY;
26
27 for (int i = 0; i < n; i++) {
28 int j = upperBound(dp, nums.get(i));
29 if (dp[j-1] < nums.get(i) && nums.get(i) < dp[j]) {
30 dp[j] = nums.get(i);
31 }
32 }
33
34 int ans = 0;
35 for (int i = 0; i <= n; i++) {
36 if (dp[i] < INFINITY) {
37 ans = i;
38 }
39 }
40 return ans;
41 }
42
43 public static List<String> splitWords(String s) {
44 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
45 }
46
47 public static void main(String[] args) {
48 Scanner scanner = new Scanner(System.in);
49 List<Integer> nums = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
50 scanner.close();
51 int res = longestSubLen(nums);
52 System.out.println(res);
53 }
54}
551function upperBound(dp, target) {
2 let n = dp.length;
3 let lo = 0, hi = n;
4 while (lo < hi) {
5 let mid = Math.floor(lo + (hi - lo) / 2);
6 if (dp[mid] > target) {
7 hi = mid;
8 } else {
9 lo = mid + 1;
10 }
11 }
12 return lo;
13}
14function longestSubLen(nums) {
15 let n = nums.length;
16 const INFINITY = Number.MAX_VALUE;
17 let dp = new Array(n + 1).fill(INFINITY);
18 dp[0] = -INFINITY;
19
20 for (let i = 0; i < n; i++) {
21 let j = upperBound(dp, nums[i]);
22 if (dp[j-1] < nums[i] && nums[i] < dp[j]) {
23 dp[j] = nums[i];
24 }
25 }
26
27 let ans = 0;
28 for (let i = 0; i <= n; i++) {
29 if (dp[i] < INFINITY) {
30 ans = i;
31 }
32 }
33 return ans;
34}
35
36function splitWords(s) {
37 return s == "" ? [] : s.split(' ');
38}
39
40function* main() {
41 const nums = splitWords(yield).map((v) => parseInt(v));
42 const res = longestSubLen(nums);
43 console.log(res);
44}
45
46class EOFError extends Error {}
47{
48 const gen = main();
49 const next = (line) => gen.next(line