Chuỗi Tăng Liên Tiếp Dài Nhất
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho dãy số nguyên $a_1, a_2, \dots, a_N$. Hãy tìm độ dài của đoạn con liên tiếp tăng ngặt dài nhất (tức là $a_l < a_{l+1} < \dots < a_r$).
Cấu trúc con tối ưu: gọi $dp[i]$ là độ dài đoạn tăng liên tiếp dài nhất kết thúc tại $i$. Nếu $a_i > a_{i-1}$ thì $dp[i] = dp[i-1] + 1$, ngược lại $dp[i] = 1$.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, \dots, a_N$ ($|a_i| \le 10^9$).
Dữ liệu ra
- In ra độ dài đoạn tăng liên tiếp dài nhất.
Ví dụ
| Input | Output |
|---|---|
| 6\n1 3 5 4 7 8 | 3 |
| 5\n5 4 3 2 1 | 1 |
Giới hạn
- $1 \le N \le 10^5$
- $|a_i| \le 10^9$
Community Discussion