VOI 07 Bài 1 - Dãy con không giảm dài nhất
Xem dạng PDFCho dãy số nguyên dương ~a_{1}~, ~a_{2}~, ..., ~a_{n}~.
Dãy số: ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~ thỏa mãn ~a_{i} \leq a_{i+1} \leq \dots \leq a_{j}~ . Với ~1 \leq i \leq j \leq n~ được gọi là dãy con không giảm của dãy số đã cho và khi đó số ~j-i+1~ được gọi là độ dài của dãy con này.
Yêu cầu: Trong số các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy số {~u_{k}~} xác định bởi ~u_{1} = 1~, ~u_k = u_{k-1} + k~ ~(k \geq 2)~, hãy tìm dãy con có độ dài lớn nhất.
Input
Dòng đầu tiên chứa một số nguyên dương ~n~ ~(n \leq 10^{4})~.
Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương ~a_{i}~ ~(a_{i} \leq 10^{8})~ là số hạng thứ ~i~ của dãy số đã cho, ~i = 1, 2, \dots, n~.
Output
Gồm 1 dòng duy nhất ghi số nguyên ~d~ là độ dài của dãy con không giảm tìm được (quy ước rằng nếu không có dãy con nào thỏa mãn điều kiện đặt ra thì ~d = 0~).
Sample Input
8
2
2007
6
6
15
16
3
21
Sample Output
3
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.