# 1. Tóm tắt đề bài

Cho dãy $nums$, tìm độ dài dãy con tăng nghiêm ngặt dài nhất.

### Giới hạn

$1 \le nums.length \le 2500$
$-10^4 \le nums[i] \le 10^4$

# 2. Hướng giải

Có 2 cách: cách 1 là dp, cách 2 là dp kết hợp chặt nhị phân.

# 3. Cách giải

Cách 1: Gọi $dp(i)$ là độ dài dãy con tăng nghiêm ngặt dài nhất kết thúc ở $i$. Ta sẽ có:

$dp(i) = max(dp(j)) + 1$

với mọi $j$ sao cho $nums[j] < nums[i]$.

Cách 2: Gọi $dp(i)$ là giá trị của phần tử cuối cùng của dãy con tăng nghiêm ngặt độ dài $i$. Để cập nhật dp, tại mỗi vị trí $nums[i]$ ta tìm vị trí $j$ trên mảng $dp$ sao cho $dp(j) < nums[i]$ và $j$ max. Sau đó, ta cập nhật vị trí $dp(j+1) = min(dp(j+1), nums[i])$.

Công thức dp kia sẽ có nghĩa: Lấy xâu con dài nhất có thể (là độ dài $j$ ta tìm) mà có thể ghép $nums[i]$ vào cuối dãy, ta được 1 xâu con tăng dài nhất kết thúc tại $nums[i]$ và có độ dài $j+1$. Vì thế, ta cập nhật vào $dp(j+1)$.

Với công thức và định nghĩa như trên, ta sẽ có: $dp(i) > dp(i-1) > dp(i-2)...$ Chứng minh thì mọi người có thể tự làm. Và vì thế ta có thể chặt nhị phân trên dãy $dp$ để tìm $j$, giảm độ phức tạp bài toán xuống.

### Độ phức tạp thuật toán

Thời gian:
Cách 1: $O(n^2)$
Cách 2: $O(n\log{n})$

### Code:

[Cách 2](https://leetcode.com/problems/longest-increasing-subsequence/submissions/1137239642/)

# 4. Nhận xét

Bài này là 1 bài toán kinh điển trong làng dp, mình nghĩ ai cũng đã biết rùi và sẽ ko đọc tutorial này của mình đâu ( .\_.). Các bạn có thể đọc thêm tại:
https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/
https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
https://cp-algorithms.com/sequences/longest_increasing_subsequence.html