Elearning CodePath – CTP Online Judge

Dãy con Tăng dài nhất

DP4_01_LIS

🟢 Hard #Dynamic Programming #Interval

### 📌 Thông tin chung

---
### 📝 Định nghĩa

Cho dãy $N$ phần tử $A = (A_1, A_2, \dots, A_N)$.

**Dãy con** (Subsequence) là một dãy thu được bằng cách xóa đi 0 hoặc nhiều phần tử khỏi dãy $A$ mà không thay đổi thứ tự của các phần tử còn lại. (Dãy con có thể không liên tiếp).

**Dãy con Tăng** là dãy con $A_{i_1}, A_{i_2}, \dots, A_{i_k}$ sao cho $i_1 < i_2 < \dots < i_k$ và $A_{i_1} < A_{i_2} < \dots < A_{i_k}$.

---
### 📝 Yêu cầu

Tìm độ dài của dãy con tăng dài nhất (LIS) trong dãy đã cho.

---
### 📥 Định dạng Đầu vào

* Dòng thứ nhất chứa số nguyên	$N$.
* Dòng thứ 2 chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.

Giới hạn:
* $1 \le N \le 100$.

---
### 📤 Định dạng Đầu ra

Kết quả mỗi test trên một dòng, là độ dài dãy con tăng dài nhất.

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `9` <br> `5 3 4 9 2 8 6 7 1`  | `4` |

**Giải thích Ví dụ:**
* **Test 1:** Dãy `5 3 4 9 2 8 6 7 1`. Dãy con tăng dài nhất là $(3, 4, 6, 7)$ hoặc $(3, 4, 6, 8)$. Độ dài là **4**.

---
### 🏷 Ràng buộc

`1 ≤ n ≤ 2·10^5`, `|ai| ≤ 10^9`.

### Phân chia subtask

| Subtask | Điểm | Ràng buộc |
|---:|---:|---|
| 1 | 30% | n ≤ 25 |
| 2 | 30% | n ≤ 2000 |
| 3 | 40% | n ≤ 2·10^5 |

---

✅ Đã AC: 8 / 31 submissions