Facebook Pixel

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:

1# function to generate all 2^N subsets and store them into the list subsets
2def generate_subsets(nums: list[int]) -> list[list[int]]:
3    n = len(nums)
4    res: list[list[int]] = [[]]
5
6    def dfs(i, cur):
7        if i == n:
8            return
9        res.append(cur + [nums[i]])
10        dfs(i + 1, cur + [nums[i]])
11        dfs(i + 1, cur)
12
13    dfs(0, [])
14    return res
15
16# function to check if list nums is strictly increasing
17def is_increasing(nums: list[int]) -> bool:
18    return all(nums[i - 1] < nums[i] for i in range(1, len(nums)))
19
20# function to get all subsequence and find longest increasing subsequence
21def longest_sub_len(nums: list[int]) -> int:
22    subsets = generate_subsets(nums)
23    mx_len = 0
24    for subset in subsets:
25        if is_increasing(subset):
26            mx_len = max(mx_len, len(subset))
27    return mx_len
28
29if __name__ == "__main__":
30    nums = [int(x) for x in input().split()]
31    res = longest_sub_len(nums)
32    print(res)
33
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
1function longestSubLen(nums: number[]): number {
2    let lis = 0; // answer
3    const n = nums.length;
4    const memo = new Array(n + 1).fill(0);
5
6    function f(i: number): number {
7        if (i === 0) {
8            return 0;
9        }
10        if (memo[i] !== 0) { // if already computed, use said answer
11            return memo[i];
12        }
13        let len = f(0) + 1; // begin with starting a new LIS
14        const ni = nums[i - 1];
15
16        // try building upon a pre-existing LIS
17        for (let j = 1; j < i; j++) {
18            const nj = nums[j - 1];
19            const fOfJ = f(j); // compute f(j), otherwise it may never be computed
20            if (nj < ni) {
21                len = Math.max(len, fOfJ + 1);
22            }
23        }
24        // LIS can end anywhere in the sequence due to the definition of our state, so update each time
25        lis = Math.max(lis, len);
26
27        memo[i] = len;
28        return len;
29    }
30
31    f(n);
32    return lis;
33}
34
35function splitWords(s: string): string[] {
36    return s === "" ? [] : s.split(" ");
37}
38
39function* main() {
40    const nums = splitWords(yield).map((v) => parseInt(v));
41    const res = longestSubLen(nums);
42    console.log(res);
43}
44
45class EOFError extends Error {}
46{
47    const gen = main();
48    const next = (line?: string) => gen.next(line ?? "").done && process.exit();
49    let buf = "";
50    next();
51    process.stdin.setEncoding("utf8");
52    process.stdin.on("data", (data) => {
53        const lines = (buf + data).split("\n");
54        buf = lines.pop() ?? "";
55        lines.forEach(next);
56    });
57    process.stdin.on("end", () => {
58        buf && next(buf);
59        gen.throw(new EOFError());
60    });
61}
62
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:

First slide
First slide
First slide
First slide
First slide
First slide

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:

1def longest_sub_len(nums: list[int]) -> int:
2    lis = 0  # answer
3    n = len(nums)
4    memo = [0] * (n + 1)
5
6    def f(i: int) -> int:
7        nonlocal lis
8
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        length = f(0) + 1  # begin with starting a new LIS
16        ni = nums[i - 1]
17        for j in range(1, i):  # try building upon a pre-existing LIS
18            nj = nums[j - 1]
19            # compute f(j), otherwise if nums[i] < nums[j] then f(j) will never be computed
20            f_of_j = f(j)
21            if nj < ni:
22                length = max(length, f_of_j + 1)
23
24        # LIS can end anywhere in the sequence due to the definition of our state, so update each time
25        lis = max(lis, length)
26
27        memo[i] = length
28        return length
29
30    f(n)
31    return lis
32
33if __name__ == "__main__":
34    nums = [int(x) for x in input().split()]
35    res = longest_sub_len(nums)
36    print(res)
37
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
1function longestSubLen(nums: number[]): number {
2    let lis = 0; // answer
3    const n = nums.length;
4    const memo = new Array(n + 1).fill(0);
5
6    function f(i) {
7        if (i === 0) {
8            return 0;
9        }
10        // if already computed, use said answer
11        if (memo[i] !== 0) {
12            return memo[i];
13        }
14        let len = f(0) + 1; // begin with starting a new LIS
15        const ni = nums[i - 1];
16
17        // try building upon a pre-existing LIS
18        for (let j = 1; j < i; j++) {
19            const nj = nums[j - 1];
20            const fOfJ = f(j); // compute f(j), otherwise it may never be computed
21            if (nj < ni) {
22                len = Math.max(len, fOfJ + 1);
23            }
24        }
25        // LIS can end anywhere in the sequence due to the definition of our state, so update each time
26        lis = Math.max(lis, len);
27
28        memo[i] = len;
29        return len;
30    }
31
32    f(n);
33    return lis;
34}
35
36function splitWords(s: string): string[] {
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?: string) => gen.next(line ?? "").done && process.exit();
50    let buf = "";
51    next();
52    process.stdin.setEncoding("utf8");
53    process.stdin.on("data", (data) => {
54        const lines = (buf + data).split("\n");
55        buf = lines.pop() ?? "";
56        lines.forEach(next);
57    });
58    process.stdin.on("end", () => {
59        buf && next(buf);
60        gen.throw(new EOFError());
61    });
62}
63
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:

First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide

Here is the implementation of the idea:

1def longest_sub_len(nums: list[int]) -> int:
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
10        # first we try starting a new sequence
11        dp[i] = dp[0] + 1
12        # then try extending an existing LIS from indices less than i
13        for j in range(1, i):
14            nj = nums[j - 1]
15            if nj < ni:
16                dp[i] = max(dp[i], dp[j] + 1)
17
18        max_len = max(max_len, dp[i])
19
20    return max_len
21
22if __name__ == "__main__":
23    nums = [int(x) for x in input().split()]
24    res = longest_sub_len(nums)
25    print(res)
26
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
1function longestSubLen(nums: number[]): number {
2    let lis = 0; // answer
3    const n = nums.length;
4    const dp = new Array(n + 1).fill(0);
5
6    dp[0] = 0; // base case: no elements has an LIS of length 0
7    let len = 0;
8    for (let i = 1; i <= n; ++i) {
9        const ni = nums[i - 1];
10
11        // first we try starting a new sequence
12        dp[i] = dp[0] + 1;
13        // then try extending an existing LIS from indices less than i
14        for (let j = 1; j < i; ++j) {
15            const nj = nums[j - 1];
16            if (nj < ni) {
17                dp[i] = Math.max(dp[i], dp[j] + 1);
18            }
19        }
20
21        len = Math.max(len, dp[i]);
22    }
23    return len;
24}
25
26function splitWords(s: string): string[] {
27    return s === "" ? [] : s.split(" ");
28}
29
30function* main() {
31    const nums = splitWords(yield).map((v) => parseInt(v));
32    const res = longestSubLen(nums);
33    console.log(res);
34}
35
36class EOFError extends Error {}
37{
38    const gen = main();
39    const next = (line?: string) => gen.next(line ?? "").done && process.exit();
40    let buf = "";
41    next();
42    process.stdin.setEncoding("utf8");
43    process.stdin.on("data", (data) => {
44        const lines = (buf + data).split("\n");
45        buf = lines.pop() ?? "";
46        lines.forEach(next);
47    });
48    process.stdin.on("end", () => {
49        buf && next(buf);
50        gen.throw(new EOFError());
51    });
52}
53
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:

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

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
2
3def upper_bound(dp, target):
4    n = len(dp)
5    lo = 0
6    hi = 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: list[int]) -> int:
16    n = len(nums)
17    dp = [inf] * (n + 1)
18    dp[0] = -inf
19
20    for i in range(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(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)
35
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
1function longestSubLen(nums: number[]): number {
2  let lis = 0; // answer
3  const n = nums.length;
4  const dp = new Array(n + 1).fill(0);
5
6  dp[0] = 0; // base case: no elements has an LIS of length 0
7  let len = 0;
8  for (let i = 1; i <= n; ++i) {
9      const ni = nums[i - 1];
10
11      // first we try starting a new sequence
12      dp[i] = dp[0] + 1;
13      // then try extending an existing LIS from indices less than i
14      for (let j = 1; j < i; ++j) {
15          const nj = nums[j - 1];
16          if (nj < ni) {
17              dp[i] = Math.max(dp[i], dp[j] + 1);
18          }
19      }
20      len = Math.max(len, dp[i]);
21  }
22  return len;
23}
24
25function splitWords(s: string): string[] {
26    return s === "" ? [] : s.split(" ");
27}
28
29function* main() {
30    const nums = splitWords(yield).map((v) => parseInt(v));
31    const res = longestSubLen(nums);
32    console.log(res);
33}
34
35class EOFError extends Error {}
36{
37    const gen = main();
38    const next = (line?: string) => gen.next(line ?? "").done && process.exit();
39    let buf = "";
40    next();
41    process.stdin.setEncoding("utf8");
42    process.stdin.on("data", (data) => {
43        const lines = (buf + data).split("\n");
44        buf = lines.pop() ?? "";
45        lines.forEach(next);
46    });
47    process.stdin.on("end", () => {
48        buf && next(buf);
49        gen.throw(new EOFError());
50    });
51}
52
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.

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro
Favorite (idle)