💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Dãy con Tăng dài nhất
DP002
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên Bài Toán** | Dãy con Tăng dài nhất (Longest Increasing Subsequence - LIS) | | **Nguồn** | Bài toán Dãy / Quy hoạch Động (DP). | | **Tên File Input** | `LIS.INP` (Giả định) | | **Tên File Output** | `LIS.OUT` (Giả định) | --- ### 📝 Đị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` <br> `9` <br> `5 3 4 9 2 8 6 7 1` <br> `7` <br> `1 2 3 10 4 5 6` | `4` <br> `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
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng