Elearning CodePath – CTP Online Judge

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

DP002

🟢 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 đầu tiên chứa số nguyên $T$ là số lượng tests ($1 \le T \le 25$).
* Mỗi test cho trên 2 dòng:
    * 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 |
| :---: | :---: |
| `2` `9` `5 3 4 9 2 8 6 7 1` `7` `1 2 3 10 4 5 6` | `4` `6` |

**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**.
* **Test 2:** Dãy `1 2 3 10 4 5 6`. Dãy con tăng dài nhất là $(1, 2, 3, 4, 5, 6)$. Độ dài là **6**.

---
### 🏷 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 | Kỹ thuật (Giả định) | Tỷ lệ điểm |
| :--- | :--- | :--- | :--- |
| $1$ | $T \le 25, N \le 100$ | $O(T \cdot N^2)$ (Quy hoạch động) | $100\%$ |

---

✅ Đã AC: 0 / 3 submissions