SPSEQ spoj – Sequences

Contact for work: 096.1014.106 (Mr. Tiến)

Nguồn đề bài: http://vn.spoj.com/problems/SPSEQ/

1. Đề bài SPSEQ spoj

W. là 1 dãy các số nguyên dương. Nó có các đặc điểm sau:

– Độ dài của dãy là 1 số lẻ: L = 2*N + 1

N + 1 số nguyên đầu tiên của dãy tạo thành 1 dãy tăng

– N + 1 số nguyên cuối của dãy tạo thành 1 dãy giảm

– Không có 2 số nguyên nào cạnh nhau trong dãy có giá trị bằng nhau

Ví dụ: 1, 2, 3, 4, 5, 4, 3, 2, 1 là 1 dãy W. độ dài 9. Tuy nhiên, dãy 1, 2, 3, 4, 5, 4, 3, 2, 2 không là 1 dãy W.

Yêu cầu: Trong các dãy con của dãy số cho trước, tìm dãy W. có độ dài dài nhất.

Input

Dòng 1: số nguyên dương N (N <= 100000), độ dài dãy số.

Dòng 2: N số nguyên dương ai (ai <= 109).

Output

1 số nguyên dương duy nhất là độ dài dãy W. dài nhất.

Example

Input:
10
1 2 3 4 5 4 3 2 1 10

Output:
9

Input:
19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1

Output:
9

2. hướng dẫn SPSEQ spoj

+Mảng QHĐ:
 – T[i] độ dãy con tăng dài nhất từ 1 -> i nhận a[i] làm phần tử cuối cùng
 S[i] độ dãy con tăng dài nhất từ n -> i nhận a[i] làm phần tử cuối cùng
 – 2 mảng trên tính bằng bài LIS
+Kết quả : res = max{2 * min(F[i], S[i]) – 1} với i = 1 -> n

3. code tham khảo SPSEQ spoj

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *