Dãy giống nhau
Xem PDF
Nộp bài
Điểm:
1500 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Dạng bài
Cho dãy a gồm n phần tử. Tìm độ dài dãy con liên tiếp xuất hiện hai lần dưới dạng hai dãy con không chồng chéo nhau.
Nói cách khác dãy [l_1,r_1] và [l_2,r_2] được gọi là giống nhau khi:
- 1\le l_1\le r_1 < l_2\le r_2\le n.
- Với mọi l_1\le i \le r_1 và l_2\le j \le r_2 thì a_i=a_j.
- r_1-l_1+1=r_2-l_2+1.
Yêu cầu: hãy tìm độ dài lớn nhất dãy con thỏa mãn điều kiện trên.
Input và Output
Input (SAME.INP)
- Dòng đầu tiên chứa số nguyên dương n (n \le 5\times10^4) ;
- Dòng thứ hai gồm n số nguyên dương a_i (1\le i \le n, a_i\le 10).
Output (SAME.OUT)
- Ghi ra màn hình một số nguyên duy nhất là kết quả của bài toán.
Subtask
- Subtask 1:(40\%) n\le60.
- Subtask 2:(60\%) không có giới hạn gì thêm.
Sample 1
Input (SAME.INP)
10
1 2 1 2 3 2 1 2 4 3
Output (SAME.OUT)
3
Bình luận