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)
35

1import 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}
60

1"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}
70

1#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}
65

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:

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)
39

1import 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}
52

1"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}
65

1#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}
56

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:

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)
28

1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int longestSubLen(List<Integer> nums) {
8        int N = nums.size();
9        int[] dp = new int[N + 1];
10
11        dp[0] = 0; // base case: no elements has an LIS of length 0
12        int len = 0;
13        for (int i = 1; i <= N; ++i) {
14            int ni = nums.get(i - 1);
15
16            // first we try starting a new sequence
17            dp[i] = dp[0] + 1;
18            // then try extending an existing LIS from indices less than i
19            for (int j = 1; j < i; ++j) {
20                int nj = nums.get(j - 1);
21                if (nj < ni) {
22                    dp[i] = Math.max(dp[i], dp[j] + 1);
23                }
24            }
25
26            len = Math.max(len, dp[i]);
27        }
28        return len;
29    }
30
31    public static List<String> splitWords(String s) {
32        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
33    }
34
35    public static void main(String[] args) {
36        Scanner scanner = new Scanner(System.in);
37        List<Integer> nums = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
38        scanner.close();
39        int res = longestSubLen(nums);
40        System.out.println(res);
41    }
42}
43

1"use strict";
2
3function longestSubLen(nums) {
4    const n = nums.length;
5    const dp = new Array(n + 1).fill(0);
6
7    dp[0] = 0; // base case: no elements has an LIS of length 0
8    let len = 0;
9    for (let i = 1; i <= n; ++i) {
10        const 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 (let j = 1; j < i; ++j) {
16            const nj = nums[j - 1];
17            if (nj < ni) {
18                dp[i] = Math.max(dp[i], dp[j] + 1);
19            }
20        }
21
22        len = Math.max(len, dp[i]);
23    }
24    return len;
25}
26
27function splitWords(s) {
28    return s === "" ? [] : s.split(" ");
29}
30
31function* main() {
32    const nums = splitWords(yield).map((v) => parseInt(v));
33    const res = longestSubLen(nums);
34    console.log(res);
35}
36
37class EOFError extends Error {}
38{
39    const gen = main();
40    const next = (line) => gen.next(line).done && process.exit();
41    let buf = "";
42    next();
43    process.stdin.setEncoding("utf8");
44    process.stdin.on("data", (data) => {
45        const lines = (buf + data).split("\n");
46        buf = lines.pop();
47        lines.forEach(next);
48    });
49    process.stdin.on("end", () => {
50        buf && next(buf);
51        gen.throw(new EOFError());
52    });
53}
54

1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int longest_sub_len(std::vector<int>& nums) {
9    int N = nums.size();
10    std::vector<int> dp(N + 1, 0);
11
12    dp[0] = 0; // base case: no elements has an LIS of length 0
13    int len = 0;
14    for (int i = 1; i <= N; ++i) {
15        int ni = nums[i - 1];
16
17        // first we try starting a new sequence
18        dp[i] = dp[0] + 1;
19        // then try extending an existing LIS from indices less than i
20        for (int j = 1; j < i; ++j) {
21            int nj = nums[j - 1];
22            if (nj < ni) {
23                dp[i] = std::max(dp[i], dp[j] + 1);
24            }
25        }
26
27        len = std::max(len, dp[i]);
28    }
29    return len;
30}
31
32template<typename T>
33std::vector<T> get_words() {
34    std::string line;
35    std::getline(std::cin, line);
36    std::istringstream ss{line};
37    ss >> std::boolalpha;
38    std::vector<T> v;
39    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
40    return v;
41}
42
43int main() {
44    std::vector<int> nums = get_words<int>();
45    int res = longest_sub_len(nums);
46    std::cout << res << '\n';
47}
48

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 = 0
7    hi = n
8    while lo < hi:
9        mid = (lo + hi) // 2
10        if dp[mid] > target:
11            hi = mid
12        else:
13            lo = mid + 1
14    return lo
15
16def longest_sub_len(nums: List[int]) -> int:
17    n = len(nums)
18    dp = [inf] * (n + 1)
19    dp[0] = -inf
20
21    for i in range(n):
22        j = upper_bound(dp, nums[i])
23        if dp[j - 1] < nums[i] and nums[i] < dp[j]:
24            dp[j] = nums[i]
25
26    ans = 0
27    for i in range(n + 1):
28        if dp[i] < inf:
29            ans = i
30    return ans
31
32if __name__ == "__main__":
33    nums = [int(x) for x in input().split()]
34    res = longest_sub_len(nums)
35    print(res)
36

1import 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
21    public static int longestSubLen(List<Integer> nums) {
22        int n = nums.size();
23        int[] dp = new int[n + 1];
24        Arrays.fill(dp, Integer.MAX_VALUE);
25        dp[0] = Integer.MIN_VALUE;
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] < Integer.MAX_VALUE) {
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}
55

1"use strict";
2
3function upperBound(dp, target) {
4    const n = dp.length;
5    let lo = 0;
6    let hi = n;
7    while (lo < hi) {
8        const mid = Math.floor(lo + (hi - lo) / 2);
9        if (dp[mid] > target) {
10            hi = mid;
11        } else {
12            lo = mid + 1;
13        }
14    }
15    return lo;
16}
17function longestSubLen(nums) {
18    const n = nums.length;
19    const dp = new Array(n + 1).fill(Number.MAX_VALUE);
20    dp[0] = -Number.MAX_VALUE;
21
22    for (let i = 0; i < n; i++) {
23        const j = upperBound(dp, nums[i]);
24        if (dp[j - 1] < nums[i] && nums[i] < dp[j]) {
25            dp[j] = nums[i];
26        }
27    }
28
29    let ans = 0;
30    for (let i = 0; i <= n; i++) {
31        if (dp[i] < Number.MAX_VALUE) {
32            ans = i;
33        }
34    }
35    return ans;
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}
65

1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <vector>
8
9int longest_sub_len(std::vector<int>& nums) {
10    int n = nums.size();
11    std::vector<int> dp(n + 1, std::numeric_limits<int>::max());
12    dp[0] = std::numeric_limits<int>::min();
13
14    for (int i = 0; i < n; i++) {
15        int j = upper_bound(dp.begin(), dp.end(), nums[i]) - dp.begin();
16        if (dp[j - 1] < nums[i] && nums[i] < dp[j]) {
17            dp[j] = nums[i];
18        }
19    }
20
21    int ans = 0;
22    for (int i = 0; i <= n; i++) {
23        if (dp[i] < std::numeric_limits<int>::max()) {
24            ans = i;
25        }
26    }
27    return ans;
28}
29
30template<typename T>
31std::vector<T> get_words() {
32    std::string line;
33    std::getline(std::cin, line);
34    std::istringstream ss{line};
35    ss >> std::boolalpha;
36    std::vector<T> v;
37    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
38    return v;
39}
40
41int main() {
42    std::vector<int> nums = get_words<int>();
43    int res = longest_sub_len(nums);
44    std::cout << res << '\n';
45}
46

Once again, the final runtime is O(n log n) where n is the number of elements in nums since for each element we use O(log n) time to update the dp array. The space complexity is O(n) due to the use of the dp array.

This is an interesting problems because unlike the previous dynamic programming problems our solution depends on the solution of a dynamic number of subproblems.