Longest Increasing Subsequence
Input
nums: the integer sequence
Output
the length of longest increasing subsequence
Examples
Example 1:
Input:
nums = [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:
nums = [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:
1from typing import List
2
3# function to generate all 2^N subsets and store them into the list subsets
4def generate_subsets(nums: List[int]) -> List[List[int]]:
5 n = len(nums)
6 res: List[List[int]] = [[]]
7
8 def dfs(i, cur):
9 if i == n:
10 return
11 res.append(cur + [nums[i]])
12 dfs(i + 1, cur + [nums[i]])
13 dfs(i + 1, cur)
14
15 dfs(0, [])
16 return res
17
18# function to check if list nums is strictly increasing
19def is_increasing(nums: List[int]) -> bool:
20 return all(nums[i - 1] < nums[i] for i in range(1, len(nums)))
21
22# function to get all subsequence and find longest increasing subsequence
23def longest_sub_len(nums: List[int]) -> int:
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
31if __name__ == "__main__":
32 nums = [int(x) for x in input().split()]
33 res = longest_sub_len(nums)
34 print(res)
351import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4import java.util.Scanner;
5import java.util.stream.Collectors;
6
7class Solution {
8 // function to generate all 2^N subsets and store them into the list subsets
9 public static void dfs(int i, List<Integer> cur, List<Integer> nums, List<List<Integer>> res) {
10 if (i == nums.size()) return;
11 cur.add(nums.get(i));
12 res.add(new ArrayList<>(cur));
13 dfs(i + 1, cur, nums, res);
14 cur.remove(cur.size() - 1);
15 dfs(i + 1, cur, nums, res);
16 }
17
18 public static List<List<Integer>> generateSubsets(List<Integer> nums) {
19 List<List<Integer>> res = new ArrayList<>();
20 res.add(new ArrayList<>());
21 dfs(0, new ArrayList<>(), nums, res);
22 return res;
23 }
24
25 // function to check if list nums is strictly increasing
26 public static boolean isIncreasing(List<Integer> nums) {
27 int N = nums.size();
28 for (int i = 1; i < N; ++i) {
29 if (nums.get(i - 1) >= nums.get(i)) {
30 return false;
31 }
32 }
33 return true;
34 }
35
36 // function to get all subsequence and find longest increasing subsequence
37 public static int longestSubLen(List<Integer> nums) {
38 List<List<Integer>> subsets = generateSubsets(nums);
39 int mxLen = 0;
40 for (List<Integer> subset : subsets) {
41 if (isIncreasing(subset)) {
42 mxLen = Math.max(mxLen, subset.size());
43 }
44 }
45 return mxLen;
46 }
47
48 public static List<String> splitWords(String s) {
49 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
50 }
51
52 public static void main(String[] args) {
53 Scanner scanner = new Scanner(System.in);
54 List<Integer> nums = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
55 scanner.close();
56 int res = longestSubLen(nums);
57 System.out.println(res);
58 }
59}
601"use strict";
2
3// function to generate all 2^N subsets and store them into the list subsets
4function generateSubsets(nums) {
5 const res = [[]];
6 function dfs(i, cur) {
7 if (i === nums.length) {
8 return;
9 }
10 cur.push(nums[i]);
11 res.push([...cur]);
12 dfs(i + 1, cur);
13 cur.pop();
14 dfs(i + 1, cur);
15 }
16 dfs(0, []);
17 return res;
18}
19
20// function to check if list nums is strictly increasing
21function isIncreasing(nums) {
22 const n = nums.length;
23 for (let 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
32function longestSubLen(nums) {
33 const subsets = generateSubsets(nums);
34 let mxLen = 0;
35 for (const subset of subsets) {
36 if (isIncreasing(subset)) {
37 mxLen = Math.max(mxLen, subset.length);
38 }
39 }
40 return mxLen;
41}
42
43function splitWords(s) {
44 return s === "" ? [] : s.split(" ");
45}
46
47function* main() {
48 const nums = splitWords(yield).map((v) => parseInt(v));
49 const res = longestSubLen(nums);
50 console.log(res);
51}
52
53class EOFError extends Error {}
54{
55 const gen = main();
56 const next = (line) => gen.next(line).done && process.exit();
57 let buf = "";
58 next();
59 process.stdin.setEncoding("utf8");
60 process.stdin.on("data", (data) => {
61 const lines = (buf + data).split("\n");
62 buf = lines.pop();
63 lines.forEach(next);
64 });
65 process.stdin.on("end", () => {
66 buf && next(buf);
67 gen.throw(new EOFError());
68 });
69}
701#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8// function to generate all 2^N subsets and store them into the list subsets
9void dfs(int i, std::vector<int>& cur, std::vector<int>& nums, std::vector<std::vector<int>>& res) {
10 if (i == nums.size()) return;
11 cur.emplace_back(nums[i]);
12 res.emplace_back(cur);
13 dfs(i + 1, cur, nums, res);
14 cur.pop_back();
15 dfs(i + 1, cur, nums, res);
16}
17
18std::vector<std::vector<int>> generate_subsets(std::vector<int>& nums) {
19 std::vector<std::vector<int>> res;
20 res.emplace_back();
21 std::vector<int> cur;
22 dfs(0, cur, nums, res);
23 return res;
24}
25
26// function to check if list nums is strictly increasing
27bool is_increasing(std::vector<int>& nums) {
28 int N = nums.size();
29 for (int i = 1; i < N; ++i) {
30 if (nums[i - 1] >= nums[i]) {
31 return false;
32 }
33 }
34 return true;
35}
36
37// function to get all subsequence and find longest increasing subsequence
38int longest_sub_len(std::vector<int>& nums) {
39 std::vector<std::vector<int>> subsets = generate_subsets(nums);
40 int mx_len = 0;
41 for (auto& subset : subsets) {
42 if (is_increasing(subset)) {
43 mx_len = std::max(mx_len, static_cast<int>(subset.size()));
44 }
45 }
46 return mx_len;
47}
48
49template<typename T>
50std::vector<T> get_words() {
51 std::string line;
52 std::getline(std::cin, line);
53 std::istringstream ss{line};
54 ss >> std::boolalpha;
55 std::vector<T> v;
56 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
57 return v;
58}
59
60int main() {
61 std::vector<int> nums = get_words<int>();
62 int res = longest_sub_len(nums);
63 std::cout << res << '\n';
64}
65DFS + 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:
1from typing import List
2
3def longest_sub_len(nums: List[int]) -> int:
4 lis = 0 # answer
5 n = len(nums)
6 memo = [0] * (n + 1)
7
8 def f(i: int) -> int:
9 nonlocal lis
10
11 if i == 0:
12 return 0
13
14 if memo[i] != 0: # if already computed, use said answer
15 return memo[i]
16
17 length = f(0) + 1 # begin with starting a new LIS
18 ni = nums[i - 1]
19 for j in range(1, i): # try building upon a pre-existing LIS
20 nj = nums[j - 1]
21 # compute f(j), otherwise if nums[i] < nums[j] then f(j) will never be computed
22 f_of_j = f(j)
23 if nj < ni:
24 length = max(length, f_of_j + 1)
25
26 # LIS can end anywhere in the sequence due to the definition of our state, so update each time
27 lis = max(lis, length)
28
29 memo[i] = length
30 return length
31
32 f(n)
33 return lis
34
35if __name__ == "__main__":
36 nums = [int(x) for x in input().split()]
37 res = longest_sub_len(nums)
38 print(res)
391import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int lis = 0; // global variable to store answer
8
9 public static int f(int i, List<Integer> nums, int[] memo) {
10 if (i == 0) {
11 return 0;
12 }
13 if (memo[i] != 0) { // if already computed, use said answer
14 return memo[i];
15 }
16 int len = f(0, nums, memo) + 1; // begin with starting a new LIS
17 int ni = nums.get(i - 1);
18
19 for (int j = 1; j < i; j++) { // try building upon a pre-existing LIS
20 int nj = nums.get(j - 1);
21 int fOfJ = f(j, nums, memo); // compute f(j), otherwise if nums[i] < nums[j] then f(j) will never be computed
22 if (nj < ni) {
23 len = Math.max(len, fOfJ + 1);
24 }
25 }
26 // LIS can end anywhere in the sequence due to the definition of our state, so update each time
27 lis = Math.max(lis, len);
28
29 memo[i] = len;
30 return len;
31 }
32 public static int longestSubLen(List<Integer> nums) {
33 int n = nums.size();
34 int[] memo = new int[n + 1];
35 Arrays.fill(memo, 0);
36 f(n, nums, memo);
37 return lis;
38 }
39
40 public static List<String> splitWords(String s) {
41 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
42 }
43
44 public static void main(String[] args) {
45 Scanner scanner = new Scanner(System.in);
46 List<Integer> nums = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
47 scanner.close();
48 int res = longestSubLen(nums);
49 System.out.println(res);
50 }
51}
521"use strict";
2
3function longestSubLen(nums) {
4 let lis = 0; // answer
5 const n = nums.length;
6 const memo = new Array(n + 1).fill(0);
7
8 function f(i) {
9 if (i === 0) {
10 return 0;
11 }
12 // if already computed, use said answer
13 if (memo[i] !== 0) {
14 return memo[i];
15 }
16 let len = f(0) + 1; // begin with starting a new LIS
17 const ni = nums[i - 1];
18
19 // try building upon a pre-existing LIS
20 for (let j = 1; j < i; j++) {
21 const nj = nums[j - 1];
22 const fOfJ = f(j); // compute f(j), otherwise it may never be computed
23 if (nj < ni) {
24 len = Math.max(len, fOfJ + 1);
25 }
26 }
27 // LIS can end anywhere in the sequence due to the definition of our state, so update each time
28 lis = Math.max(lis, len);
29
30 memo[i] = len;
31 return len;
32 }
33
34 f(n);
35 return lis;
36}
37
38function splitWords(s) {
39 return s === "" ? [] : s.split(" ");
40}
41
42function* main() {
43 const nums = splitWords(yield).map((v) => parseInt(v));
44 const res = longestSubLen(nums);
45 console.log(res);
46}
47
48class EOFError extends Error {}
49{
50 const gen = main();
51 const next = (line) => gen.next(line).done && process.exit();
52 let buf = "";
53 next();
54 process.stdin.setEncoding("utf8");
55 process.stdin.on("data", (data) => {
56 const lines = (buf + data).split("\n");
57 buf = lines.pop();
58 lines.forEach(next);
59 });
60 process.stdin.on("end", () => {
61 buf && next(buf);
62 gen.throw(new EOFError());
63 });
64}
651#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int f(int i, std::vector<int>& nums, std::vector<int>& memo, int& lis) {
9 if (i == 0) {
10 return 0;
11 }
12 if (memo[i] != 0) { // if already computed, use said answer
13 return memo[i];
14 }
15 int len = f(0, nums, memo, lis) + 1; // begin with starting a new LIS
16 int ni = nums[i - 1];
17
18 for (int j = 1; j < i; j++) { // try building upon a pre-existing LIS
19 int nj = nums[j - 1];
20 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
21 if (nj < ni) {
22 len = std::max(len, f_of_j + 1);
23 }
24 }
25 // LIS can end anywhere in the sequence due to the definition of our state, so update each time
26 lis = std::max(lis, len);
27
28 memo[i] = len;
29 return len;
30}
31
32int longest_sub_len(std::vector<int>& nums) {
33 int n = nums.size();
34 std::vector<int> memo(n + 1, 0);
35 int lis = 0;
36 f(n, nums, memo, lis);
37 return lis;
38}
39
40template<typename T>
41std::vector<T> get_words() {
42 std::string line;
43 std::getline(std::cin, line);
44 std::istringstream ss{line};
45 ss >> std::boolalpha;
46 std::vector<T> v;
47 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
48 return v;
49}
50
51int main() {
52 std::vector<int> nums = get_words<int>();
53 int res = longest_sub_len(nums);
54 std::cout << res << '\n';
55}
56The 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:
1from typing import List
2
3def longest_sub_len(nums: List[int]) -> int:
4 n = len(nums)
5 dp = [0] * (n + 1)
6
7 dp[0] = 0 # base case: no elements has an LIS of length 0
8 max_len = 0
9 for i in range(1, n + 1):
10 ni = nums[i - 1]
11
12 # first we try starting a new sequence
13 dp[i] = dp[0] + 1
14 # then try extending an existing LIS from indices less than i
15 for j in range(1, i):
16 nj = nums[j - 1]
17 if nj < ni:
18 dp[i] = max(dp[i], dp[j] + 1)
19
20 max_len = max(max_len, dp[i])
21
22 return max_len
23
24if __name__ == "__main__":
25 nums = [int(x) for x in input().split()]
26 res = longest_sub_len(nums)
27 print(res)
281import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5