300. Longest Increasing Subsequence

Problem

Bài toán yêu cầu tìm độ dài dãy con dài nhất trong một mảng số nguyên.

💡

Subsequence (dãy con) là một dãy được tạo ra từ dãy ban đầu bằng cách xóa đi một số (hoặc không xóa) phần tử, nhưng giữ nguyên được thứ tự tương đối của các phần tử còn lại. Các phần tử trong subsequence không nhất thiết phải liên tiếp nhau trong dãy gốc, chỉ cần không thay đổi thứ tự xuất hiện ban đầu

Ví dụ:

Cho dãy gốc: A, B, C, D, E

Một số subsequence hợp lệ:

A, C, E (bỏ B và D, nhưng vẫn giữ thứ tự A trước C trước E)

B, D

A, B, C, D, E (chính nó)

A, E

Lưu ý:

Substring (xâu con) là dãy liên tiếp các phần tử trong dãy gốc.

Mọi substring đều là subsequence, nhưng không phải mọi subsequence là substring.

Tóm lại, subsequence là dãy con giữ nguyên thứ tự, không cần liên tiếp nhau

DP Solution

Ý tưởng: Với mỗi phần tử nums[i], duyệt lại tất cả các phần tử trước đó nums[j] (j < i). Nếu nums[j] < nums[i], cập nhật độ dài LIS kết thúc tại i là lớn nhất giữa giá trị hiện tại và dp[j] + 1.

Kết quả cuối cùng là giá trị lớn nhất trong mảng dp.

typescripttypescript

1function lengthOfLIS(nums: number[]): number {
2    /**
3    Approach 1: Using DP
4    dp store previous count of number of LIS
5     */
6
7    const dp: number[] = new Array(nums.length).fill(1);
8    let lis: number = 1;
9
10    for (let i = 1; i < nums.length; i++) { // O(n)
11        for (let j = 0; j < i; j++) { // O(n)
12            if (nums[i] > nums[j]) {
13                dp[i] = Math.max(dp[i], dp[j] + 1)
14            }
15        }
16
17        lis = Math.max(lis, dp[i])
18    }
19
20    return lis
21};

💡

dp[i] = Math.max(dp[i], dp[j] + 1)

dp[i] là độ dài dãy con tăng dài nhất kết thúc tại vị trí i (tức là phần tử nums[i] phải nằm ở cuối dãy con này)

Ban đầu, mỗi phần tử đều có thể là một dãy con tăng độ dài 1 (chỉ chứa chính nó), nên khởi tạo tất cả dp[i] = 1

Optimize solution - with binary search

Ta không cần biết chính xác dãy con tăng dài nhất là gì, mà chỉ cần biết độ dài của nó

Ta sẽ xây dựng một mảng tails , trong đó

tails[i] là phần tử nhỏ nhất có thể đứng ở cuối của một dãy con tăng có độ dài i + 1

Mỗi khi duyệt qua một số, ta sẽ tìm vị trí thích hợp trong tails để:

Nếu số đó lớn hơn tất cả, nối vào cuối (tăng độ dài LIS)

Nếu không, thay thế phần tử đầu tiên lớn hơn hoặc bằng số đó (giữ cho các giá trị ở tails nhỏ nhất có thể)

typescripttypescript

1function lengthOfLIS(nums: number[]): number {
2    const tails: number[] = [];
3    for (const num of nums) {
4        let left = 0, right = tails.length;
5        while (left < right) {
6            const mid = left + Math.floor((right - left) / 2)
7            if (tails[mid] < num) left = mid + 1
8            else right = mid
9        }
10        tails[left] = num
11    }
12
13    return tails.length;
14};

💡

Khi nào “thêm vào cuối”?

Khi biến left sau vòng lặp bằng đúng độ dài của mảng tails (tức là left === tails.length ) nghĩa là không có phần tử nào trong tails lớn hơn hoặc bằng num

Khi đó, câu lệnh tails[left] = num tương đương với việc thêm một phần tử mới vào cuối mảng (giống như tails.push(num) )

Khi nào là “thay thế”?

Nếu left < tails.length , nghĩa là đã tìm được một vị trí trong mảng tails có giá trị lớn hơn hoặc bằng num

Khi đó, tails[left] = num là thay thế phần tử tại vị trí đó

num	Binary Search trên `sub`	Cập nhật `sub`
10	Không có gì, thêm vào	[10]
9	Tìm vị trí thay thế: 0 (vì `9 < 10`)	[9]
2	Tìm vị trí thay thế: 0 (vì `2 < 9`)	[2]
5	Không tìm thấy, thêm vào cuối	[2, 5]
3	Tìm vị trí thay thế: 1 (vì `3 < 5`)	[2, 3]
7	Không tìm thấy, thêm vào cuối	[2, 3, 7]
101	Không tìm thấy, thêm vào cuối	[2, 3, 7, 101]
18	Tìm vị trí thay thế: 3 (vì `18 < 101`)	[2, 3, 7, 18]

Loading content...

1function lengthOfLIS(nums: number[]): number { 2 /** 3 Approach 1: Using DP 4 dp store previous count of number of LIS 5 */ 6 7 const dp: number[] = new Array(nums.length).fill(1); 8 let lis: number = 1; 9 10 for (let i = 1; i < nums.length; i++) { // O(n) 11 for (let j = 0; j < i; j++) { // O(n) 12 if (nums[i] > nums[j]) { 13 dp[i] = Math.max(dp[i], dp[j] + 1) 14 } 15 } 16 17 lis = Math.max(lis, dp[i]) 18 } 19 20 return lis 21};

1function lengthOfLIS(nums: number[]): number { 2 const tails: number[] = []; 3 for (const num of nums) { 4 let left = 0, right = tails.length; 5 while (left < right) { 6 const mid = left + Math.floor((right - left) / 2) 7 if (tails[mid] < num) left = mid + 1 8 else right = mid 9 } 10 tails[left] = num 11 } 12 13 return tails.length; 14};