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
Quan trọng là tư duy, độ tối ưu chứ đâu phải cứ AC là được.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.