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
The brute force approach generates all possible subsequences of the input array. For each element, we make a binary choice: include it or exclude it. This creates 2^N possible subsequences.
After generating each subsequence, we verify whether its elements appear in strictly increasing order. This verification takes O(N) time per subsequence. Among all valid increasing subsequences, we track the maximum length.
This approach runs in O(N * 2^N) time because we examine 2^N subsequences and spend O(N) time checking each one. The space complexity is O(N * 2^N) since we store all subsequences in memory, each potentially containing up to N elements.
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)
331import 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}
701function 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}
621#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 words "longest" and "sequence" point toward dynamic programming. We need to define a state that captures the problem structure.
Our state definition is: f(i) represents the length of the longest increasing subsequence that ends at position i (and must include nums[i]). This formulation works because any LIS must end somewhere—by computing the answer for every possible ending position, we find the global maximum.
To build an LIS ending at position i, we examine all earlier positions j < i. If nums[j] < nums[i], we can extend the LIS ending at position j by appending nums[i]. We take the maximum length among all such extensions.
The base case handles i = 0, representing an empty prefix with an LIS of length 0.
The complete recurrence:
- State:
f(i)= length of longest increasing subsequence ending atnums[i] - Base case:
f(0) = 0 - Transition:
f(i) = max(f(j) + 1)for alljwhere0 ≤ j < iandnums[j] < nums[i]
We use memoization to cache computed results and avoid redundant calculations.
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)
371import 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}
651function 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}
631#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}
56This solution runs in O(n^2) time. We compute n states, and each state examines up to n previous positions to find the maximum extension. The space complexity is O(n) for the memoization array.
Bottom-up DP
The recursive solution can be converted to an iterative one. Instead of computing states top-down with memoization, we build them bottom-up in a loop.
This works because larger indices depend only on smaller indices. When computing dp[i], all values dp[0] through dp[i-1] are already available. We process positions from left to right, filling the DP table as we go.
The implementation follows the same logic as the memoized version, but uses a loop instead of recursion:
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)
261import 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}
431"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}
541function 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}
531#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}
48This solution has the same O(n^2) time complexity as the memoized version—we fill n entries in the DP table, and each entry requires checking up to n previous positions. The space complexity remains O(n) for the DP array.
O(n log n) with DP and binary search
We can improve the time complexity by using a different DP state definition combined with binary search.
Define dp[i] as the smallest ending element among all increasing subsequences of length i. If multiple subsequences have length i, we store only the one with the smallest final element. This greedy choice gives us maximum flexibility when extending the sequence later.
Initialize dp[0] = -∞ (a sentinel value) and all other positions to ∞. As we process each element in nums, we update the DP array. The answer is the largest index i where dp[i] remains finite.
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
161function 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}
25The key observation: the dp array maintains sorted order at all times. For any index i, we have dp[i-1] ≤ dp[i]. This invariant holds because we always store the smallest possible ending element for each length.
When processing a new element nums[i], we need to find the first position in dp where the value exceeds nums[i]. This is exactly what binary search (upper bound) does in O(log n) time. We then update that position if appropriate.
By replacing the linear scan with binary search, we reduce the time per element from O(n) to O(log n), giving us O(n log n) overall.
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)
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
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}
551"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}
651function 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}
521#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}
46The final time complexity is O(n log n). We process n elements, and each one requires O(log n) time for the binary search and update. The space complexity remains O(n) for the DP array.
This problem demonstrates an important optimization technique: when a DP solution involves finding the maximum or minimum over a range of subproblems, check whether that range has exploitable structure (like sorted order) that allows binary search instead of linear scanning.