Bài toán 3: Dãy Wavio

Phát biểu bài toán

Dãy số Wavio là dãy số nguyên có dạng:

• các phần tử đầu tăng dần nghiêm ngặt đến một phần tử đỉnh,
• sau đó giảm dần nghiêm ngặt.

Ngoài ra, độ dài phần tăng và phần giảm phải bằng nhau qua đỉnh.
Nói cách khác, nếu một dãy Wavio có độ dài 2k - 1 thì:

• k phần tử đầu tạo thành một dãy tăng nghiêm ngặt,
• phần tử thứ k là đỉnh,
• k phần tử cuối tạo thành một dãy giảm nghiêm ngặt.

Ví dụ, dãy:

1 2 3 4 5 2 1

là một dãy Wavio có độ dài 7.

Cho một dãy gồm N số nguyên, hãy tìm độ dài lớn nhất của một dãy con Wavio có thể trích ra từ dãy đã cho.

Dữ liệu vào

Đọc từ file văn bản WAVIO.INP:

• Dòng 1 ghi số nguyên dương N (1 ≤ N ≤ 10000)
• Dòng 2 ghi N số nguyên a_1, a_2, ..., a_N (|a_i| ≤ 10^9)

Dữ liệu ra

Ghi ra file văn bản WAVIO.OUT:

• Một số nguyên duy nhất là độ dài lớn nhất của dãy con Wavio tìm được.

Ràng buộc

• 1 ≤ N ≤ 10000
• |a_i| ≤ 10^9

Chấm điểm

• Subtask 1 (25 điểm): 1 ≤ N ≤ 20
• Subtask 2 (35 điểm): 1 ≤ N ≤ 1000
• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.

Ví dụ

WAVIO.INP

5
2 1 4 3 5

WAVIO.OUT

3

Giải thích

Một dãy con Wavio dài nhất là:

1 4 3

Dãy này tăng đến 4, rồi giảm xuống 3, nên có độ dài 3.

Gợi ý

Gọi:

• L[i] là độ dài dãy con tăng dài nhất kết thúc tại vị trí i
• R[i] là độ dài dãy con giảm dài nhất bắt đầu từ vị trí i

Khi đó, nếu chọn a[i] làm đỉnh của dãy Wavio thì độ dài lớn nhất nhận được là:

2 * min(L[i], R[i]) - 1

Đáp án là giá trị lớn nhất của biểu thức trên với mọi i.

Để tính L[i] và R[i] hiệu quả, có thể dùng thuật toán LIS kết hợp tìm kiếm nhị phân.