Dãy con bị chặn trên-dưới
View as PDF
Submit solution
Points:
250.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem types
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Cho dãy số nguyên ~A~ gồm ~n~ số hạng ~a_1, a_2, .., a_n~. Một dãy con gồm các số hạng liên tiếp ~a_i,a_{(i+1)},..,a_j~ được gọi là dãy con bị chặn trên – dưới nếu thỏa mãn:
- ~i < j~;
- ~a_i≤a_j~;
- ~a_i≤a_k≤a_j~ với ~k = i+1,i+2,..j – 1~.
Ví dụ, dãy ~A~: 10, 2, 3, 2, 4, 7, 2. Dãy con: 2, 3, 2, 4, 7 là một dãy con bị chặn trên-dưới.
Yêu cầu: Hãy tìm một dãy con bị chặn trên-dưới của dãy ~A~ và có nhiều số hạng nhất.
Dữ liệu gồm:
- Dòng đầu ghi số nguyên dương ~n~ là số phần tử của dãy.
- Dòng thứ hai ghi ~n~ số hạng ~a_1, a_2, .., a_n~ ~(|a_i| ≤10^9)~.
Kết quả
- Số các số hạng của của dãy con bị chặn trên-dưới gồm nhiều số hạng nhất tìm được. Nếu không có dãy con bị chặn trên-dưới thì ghi -1.
Ví dụ:
Input 1
7
10 2 3 2 4 7 2
Output 1
5
Input 2
4
7 6 5 6
Output 2
2
Input 3
4
7 6 5 4
Output 3
-1
Giải thích
- Ví dụ 1: Dãy tìm được: 2, 3, 2, 4, 7
- Ví dụ 2: Dãy tìm được: 5, 6
- Không có dãy bị chặn trên - dưới
Giới hạn:
- 20% số test ứng với ~n ≤100~;
- 20% số test khác ứng với ~n ≤〖3.10^3~;
- 60% số test còn lại ứng với ~n ≤5.10^5~.
Comments
Đã có đề.