Elearning CodePath – CTP Online Judge

Dãy Hình Nón

SPSEQ

🟢 Hard #Dynamic Programming

### 📌 Thông tin chung

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

Một dãy số có độ dài (số phần tử) là $m$ được gọi là **dãy hình nón** (Cone Sequence) nếu nó là một dãy gồm các số nguyên dương và có các đặc điểm sau:

1.  **Độ dài lẻ:** Số lượng phần tử của dãy là một số lẻ (hay $m = 2 \times x + 1$).
2.  **Không có số bằng nhau kề nhau:** Không có hai số nào đứng cạnh nhau trong dãy có giá trị bằng nhau ($A_i \ne A_{i+1}$).
3.  **Tăng dần:** $x+1$ số đầu tiên của dãy là một dãy tăng nghiêm ngặt (Strictly Increasing Subsequence).
4.  **Giảm dần:** $x+1$ số cuối cùng của dãy là một dãy giảm nghiêm ngặt (Strictly Decreasing Subsequence).

*Lưu ý: Phần tử ở giữa (đỉnh nón) là phần tử lớn nhất và là chung của cả hai dãy tăng và giảm.*

Ví dụ: Dãy $\{3, 6, 9, 5, 2\}$ là một dãy hình nón có độ dài $m=5$ ($x=2$).

### Bài toán

Cho dãy $A$ gồm $N$ số nguyên dương $a_1, a_2, \dots, a_n$.
Dãy con (Subsequence) của $A$ là một dãy được tạo ra bằng cách lấy ra một số phần tử trong $A$ nhưng giữ nguyên thứ tự (các phần tử có thể không liên tiếp nhau).

Yêu cầu: Hãy tìm **độ dài của dãy con hình nón dài nhất** từ dãy $A$.

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

Dữ liệu vào từ file `SPSEQ.INP` gồm 2 dòng:

* Dòng đầu: Ghi số nguyên dương $N$ là độ dài dãy số ban đầu ($N \le 10^5$).
* Dòng thứ 2: Chứa $N$ số nguyên dương $a_1, a_2, \dots, a_n$ ($a_i \le 10^9$).

Các số trên cùng một dòng cách nhau bởi dấu cách.

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

Ghi ra file `SPSEQ.OUT` một số duy nhất là độ dài của dãy con hình nón dài nhất.

---
### ✨ Ví dụ

| Input (`SPSEQ.INP`) | Output (`SPSEQ.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `7` <br> `5 4 5 9 7 4 5` | `5` | Độ dài dãy con hình nón dài nhất là 5, có hai dãy là: <br> * $\{4, 5, 9, 7, 4\}$ (Lấy từ vị trí 2, 3, 4, 5, 6) <br> * $\{4, 5, 9, 7, 5\}$ (Lấy từ vị trí 2, 3, 4, 5, 7) |

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

| Tỷ lệ điểm | Ràng buộc |
| :--- | :--- |
| $50\%$ | $N \le 20$; $a_i \le 10^9$ |
| $50\%$ | $N \le 10^5$; $a_i \le 10^9$ |

---

✅ Đã AC: 0 / 4 submissions