Đảo Ngược Dãy Con

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John đang sắp xếp $N$ con bò thành một hàng để chụp ảnh ( $1 \leq N \leq 50$ ). Chiều cao của con bò thứ $i$ trong dãy là $a (i)$ , và Farmer John muốn dãy bò có một dãy con tăng dài nhất có thể.

Nhắc lại, một dãy con là tập hợp các phần tử $a (i_{1}), a (i_{2}), \dots, a (i_{k})$ lấy từ dãy tại các chỉ số $i_{1} < i_{2} < \dots < i_{k}$ . Dãy con được gọi là tăng nếu $a (i_{1}) \leq a (i_{2}) \leq \dots \leq a (i_{k})$ .

Để tối ưu hóa, Farmer John được phép chọn một dãy con bất kỳ và đảo ngược thứ tự các phần tử của dãy con đó (đúng một lần).

Ví dụ, nếu ta có dãy:

$1 6 2 3 4 3 5 3 4$

Ta có thể chọn dãy con ở các vị trí đánh dấu và đảo ngược:

$1 6 2 3 4 3 5 3 4 \to 1 4 2 3 4 3 3 5 6$

Lưu ý rằng dãy con sau khi đảo ngược vẫn chiếm đúng các vị trí ban đầu của nó, các phần tử còn lại không thay đổi.

Hãy tìm độ dài tối đa của dãy con tăng có thể đạt được sau khi thực hiện đúng một lần đảo ngược dãy con bất kỳ (có thể chọn dãy con rỗng, tức là không đảo gì).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ .
$N$ dòng tiếp theo, mỗi dòng chứa một số nguyên $a (i)$ ( $1 \leq a (i) \leq 50$ ).

Dữ liệu ra

In ra một số nguyên duy nhất — độ dài tối đa của dãy con tăng sau khi thực hiện một lần đảo ngược dãy con.

Ràng buộc

$1 \leq N \leq 50$
$1 \leq a (i) \leq 50$

Ví dụ

Input	Output	Giải thích
9 1 2 3 9 5 6 8 7 4	9	Đảo ngược dãy con gồm phần tử thứ 4, 5, 6, 7, 8, 9 (giá trị 9, 5, 6, 8, 7, 4) thành (4, 5, 6, 7, 8, 9), ta được dãy 1 2 3 4 5 6 7 8 9 là dãy con tăng toàn bộ có độ dài 9.
5 1 2 3 4 5	5	Dãy đã tăng sẵn, không cần đảo ngược.

Ghi chú

Dãy con tăng cho phép các phần tử bằng nhau ( $a (i_{k}) \leq a (i_{k + 1})$ ).

Bình luận

Không có bình luận tại thời điểm này.