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 a1,a2,..,an. Một dãy con gồm các số hạng liên tiếp ai,a(i+1),..,aj được gọi là dãy con bị chặn trên – dưới nếu thỏa mãn:

  • i<j;
  • aiaj;
  • aiakaj với k=i+1,i+2,..j1.

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 a1,a2,..,an (|ai|109).

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
Copy
7
10  2  3  2  4  7  2
Output 1
Copy
5
Input 2
Copy
4
7 6 5 6
Output 2
Copy
2
Input 3
Copy
4
7 6 5 4
Output 3
Copy
-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 n100;
  • 20% số test khác ứng với n3.103;
  • 60% số test còn lại ứng với n5.105.

Comments

Please read the guidelines before commenting.



  • 1
    admin  commented 1:17:40 pm, 20/01/2021

    Đã có đề.