Elearning CodePath – CTP Online Judge

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

DP002

### 📌 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

Do $N \le 100$, thuật toán Quy hoạch động $O(N^2)$ là phù hợp.

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- | 
| $1$ | $T \le 25, N \le 100$  | $100\%$ |

---

✅ Đã AC: 6 / 28 submissions