Elearning CodePath – CTP Online Judge

Đoạn Đẹp

LONGEST_SUBARRAY

🟢 Easy #General

### 📝 Bài toán

Cho một dãy gồm $N$ số nguyên dương $H = (h_1, h_2, \dots, h_n)$.

Một đoạn con liên tiếp $H[i..j]$ ($1 \le i \le j \le N$) được gọi là **"đẹp"** nếu nó là một **dãy tăng liên tiếp rồi giảm liên tiếp**.

Cụ thể, một đoạn con $H[i..j]$ là đẹp nếu tồn tại một chỉ số đỉnh $p$ ($i \le p \le j$) sao cho:
1. **Phần tăng:** Dãy $H[i..p]$ là dãy tăng chặt: $h_i < h_{i+1} < \dots < h_p$.
2. **Phần giảm:** Dãy $H[p..j]$ là dãy giảm chặt: $h_p > h_{p+1} > \dots > h_j$.

Lưu ý:
* Nếu $i = p$, phần tăng chỉ có 1 phần tử. Nếu $p = j$, phần giảm chỉ có 1 phần tử.
* **Đoạn "đẹp" tối thiểu phải có độ dài 3** để có thể chứa cả phần tăng và phần giảm (ví dụ: $a < b > c$). Tuy nhiên, nếu đề bài cho phép đoạn tăng hoặc giảm có độ dài bằng 1, thì đoạn có độ dài 1 hoặc 2 cũng có thể được xem xét.
* Dựa trên ví dụ giải thích, đoạn $2, 3, 5, 4, 3, 2, 1$ có độ dài 7 (tăng đến 5, giảm từ 5), ngụ ý rằng **phần tăng và phần giảm phải có ít nhất 2 phần tử** (trừ trường hợp đoạn chỉ tăng hoặc chỉ giảm, nhưng tên gọi "đẹp" thường ám chỉ sự thay đổi xu hướng). Với định nghĩa chặt chẽ (tăng $h_i < h_{i+1}$ và giảm $h_p > h_{p+1}$), ta cần $i \ne p$ hoặc $p \ne j$.
* Ta xác định độ dài lớn nhất của một đoạn con liên tiếp $H[i..j]$ thỏa mãn tính chất trên. Nếu không có đoạn nào, kết quả là 0.

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

Dữ liệu vào từ file `BAI2.INP`:

* Dòng đầu tiên chứa số nguyên $N$.
* Dòng thứ hai chứa $N$ số nguyên dương $h_1, h_2, \dots, h_n$.

Giới hạn: $1 \le N \le 10^5$, $1 \le h_i \le 10^6$.

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

Ghi ra file `BAI2.OUT` một dòng duy nhất chứa số nguyên – độ dài lớn nhất của một đoạn "đẹp".

---
### ✨ Ví dụ

| Input (`BAI2.INP`) | Output (`BAI2.OUT`) |
| :--- | :--- |
| `10` <br> `2 3 5 4 3 2 1 6 7 6` | `7` |

---
### 🏷 Phân Subtask

Dựa trên ràng buộc $N$ lớn, giải pháp $O(N^2)$ (duyệt tất cả các đoạn con) là không chấp nhận được.

| Subtask | Ràng buộc | Số điểm ước tính | 
| :--- | :--- | :--- | :--- |
| 1 | $N \le 1000$ | $30\%$ | 
| 2 | $N \le 10^5$ | $70\%$ |

✅ Đã AC: 3 / 3 submissions