Chuỗi Tăng Liên Tiếp Dài Nhất

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved