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
Problem Statement
Given an array of integers, find the length of the longest subsequence where elements appear in strictly increasing order. A subsequence maintains relative order but doesn't need to be contiguous.
nums = [50, 3, 10, 7, 40, 80] LIS = [3, 7, 40, 80], length = 4
Note that [3, 10, 40, 80] is also a valid LIS with the same length.
Why Greedy Fails
The obvious approach: always pick the smallest available element to maximize future options.
nums = [10, 9, 2, 5, 3, 7, 101, 18] Greedy approach: Start with smallest element 2 Build sequence: 2 → 3 → 7 → 18 Greedy result: length 4 But optimal: 2 → 3 → 7 → 101 OR 2 → 5 → 7 → 101 Also length 4 (same in this case)
Here's where greedy truly fails:
nums = [3, 10, 2, 1, 20] Greedy: pick smallest (1), then 20 → [1, 20], length 2 Optimal: [3, 10, 20], length 3
The greedy choice of starting with the smallest element (1) blocks us from the longer sequence [3, 10, 20]. The problem requires considering all possible starting points and extensions—a hallmark of dynamic programming.
Brute Force
Generate all 2^N subsequences and check each for increasing order. Track the maximum length among valid subsequences.
This runs in O(N × 2^N) time—impractical for any reasonable input size.
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}
65The Key Insight: Think Backwards
Instead of asking "what's the longest sequence starting from here?", ask: "what's the longest sequence ending at this position?"
Consider nums = [50, 3, 10, 7, 40, 80] and focus on position 4 (value 40):
nums: [50, 3, 10, 7, 40, 80] index: 0 1 2 3 4 5 ↑ current position Which earlier elements can 40 extend? - 50 at index 0: 50 > 40, can't extend - 3 at index 1: 3 < 40, CAN extend → [3, 40] - 10 at index 2: 10 < 40, CAN extend → [..., 10, 40] - 7 at index 3: 7 < 40, CAN extend → [..., 7, 40]
The best LIS ending at position 4 comes from extending the best LIS ending at an earlier position where the value is smaller than 40.
State Definition
Let dp[i] = length of the longest increasing subsequence that ends at index i.
Transition: For each position i, look at all earlier positions j where nums[j] < nums[i]. The LIS ending at i is one more than the best LIS ending at any such j.
dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
Base case: Every element by itself is an LIS of length 1.
Answer: max(dp[0], dp[1], ..., dp[n-1]) since the LIS can end anywhere.
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 converts naturally to iteration. Process positions left to right—when computing dp[i], all values dp[0] through dp[i-1] are already available.
Worked Example
The diagram shows the progression:
- Initialize: Every element starts as an LIS of length 1
- dp[2] = 2: Element 10 can extend from 3 (index 1), giving [3, 10]
- dp[4] = 3: Element 40 can extend from 10 (index 2), giving [3, 10, 40]
- dp[5] = 4: Element 80 extends the sequence to [3, 10, 40, 80]
The answer is max(dp) = 4.
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}
48Complexity Analysis
Time Complexity: O(n²)
We fill n entries in the DP table. For each entry, we examine up to n previous positions. Total: n × n = O(n²).
Space Complexity: O(n)
We store one value per position in the DP array.
Optimization: O(n log n) with Binary Search
The O(n²) bottleneck is the inner loop that scans all previous positions. Can we do better?
Key observation: We don't need to track the full LIS ending at each position. We only need to know: "what's the smallest ending value for an LIS of each length?"
New state definition:
dp[k] = smallest ending element among all increasing subsequences of length k
Why smallest? If two subsequences have the same length, the one ending with a smaller value offers more extension opportunities.
nums = [50, 3, 10, 7, 40, 80] After processing each element: [50]: dp = [50, ∞, ∞, ∞, ∞, ∞] Length 1 ends at 50 [50, 3]: dp = [3, ∞, ∞, ∞, ∞, ∞] 3 < 50, replace (smaller is better) [.., 10]: dp = [3, 10, ∞, ∞, ∞, ∞] 10 > 3, extend to length 2 [.., 7]: dp = [3, 7, ∞, ∞, ∞, ∞] 7 < 10, replace at length 2 [.., 40]: dp = [3, 7, 40, ∞, ∞, ∞] 40 > 7, extend to length 3 [.., 80]: dp = [3, 7, 40, 80, ∞, ∞] 80 > 40, extend to length 4 Answer: first ∞ is at index 4, so LIS length = 4
The dp array stays sorted. Smaller lengths can't have larger ending values (otherwise we could have extended them). This means we can use binary search to find where to place each new element.
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 O(n²) code above shows the logic clearly: for each element, scan to find where it fits. But since dp is sorted, we can replace the linear scan with binary search.
Binary search optimization: Use upper_bound to find the first position where dp[j] > nums[i]. This is where the new element belongs—either extending the longest subsequence or replacing an existing ending value with a smaller one.
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}
46Complexity Analysis (Optimized)
Time Complexity: O(n log n)
We process n elements. Each requires O(log n) for binary search. Total: n × log n.
Space Complexity: O(n)
The dp array stores at most n elements.
Summary
| Approach | Time | Space | Key Idea |
|---|---|---|---|
| Brute Force | O(n × 2^n) | O(n × 2^n) | Check all subsequences |
| DP (ending at i) | O(n²) | O(n) | dp[i] = LIS length ending at i |
| DP + Binary Search | O(n log n) | O(n) | dp[k] = smallest ending value for length k |
The key insight for both DP solutions is thinking backwards: instead of asking "where can I go from here?", ask "where did I come from?"