Elearning CodePath – CTP Online Judge

Bài toán Dãy con liên tiếp

MWSEQ

🟢 Hard #Segment Tree

### 📌 Thông tin chung

---
### 📝 Bài toán

Xét một dãy số nguyên $A$.
**Trọng số** của dãy số $A$ được định nghĩa là số phần tử của **dãy con tăng ngặt dài nhất** gồm **các phần tử liên tiếp** của dãy.

Cho dãy số nguyên $A = (A_1, A_2, \dots, A_N)$. Bạn được phép **xóa** (nếu muốn) một dãy các phần tử **liên tiếp** trong $A$.

Yêu cầu: Tìm cách xóa để dãy còn lại có trọng số lớn nhất, và cho biết trọng số lớn nhất đó.

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

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

* Dòng đầu tiên: Chứa một số nguyên dương $N$.
* Dòng thứ hai: Chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ cách nhau bởi dấu cách.

Giới hạn:
* $1 \le N \le 10^5$.
* $1 \le A_i \le 10^9$.

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

Ghi ra file `MWSEQ.OUT` một số nguyên duy nhất là trọng số lớn nhất của dãy còn lại.

---
### ✨ Ví dụ

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

Giải thích:
* Dãy ban đầu: $(5, 3, 4, 9, 2, 6, 6, 7, 1)$.
* Cách tốt nhất là xóa 3 phần tử liên tiếp $(9, 2, 6)$ (vị trí 4, 5, 6).
* Dãy còn lại: $(5, 3, 4, 6, 7, 1)$.
* Trọng số của dãy còn lại là 4, vì dãy con tăng ngặt liên tiếp dài nhất là $(3, 4, 6, 7)$.

---
### 🏷 Subtask

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

---

✅ Đã AC: 1 / 5 submissions