Ta gọi một dãy chia hết hoàn toàn là dãy a1, a2, …, aN với aj chia hết cho a¬i với i<j. Một dãy con của một dãy là một dãy được thiết lập bằng cách xoá một số phần tử nào đó trong dãy.
Ví dụ: 3, 7, 11, 3 là một dãy con của dãy 6, 3, 11, 5, 7, 4, 3, 11, 5, 3 nhưng 3, 3, 7 không phải là một dãy con của dãy 6, 3, 11, 5, 7, 4, 3, 11, 5, 3 và 3, 15, 60, 720 là một dãy chia hết.
Yêu cầu: Cho một dãy các số nguyên, tìm dãy con chia hết hoàn toàn có độ dài lớn nhất trong dãy đã cho.
Dữ liệu vào: Cho trong file SEQ.INP có cấu trúc:
• Dòng đầu chứa N là độ dài của dãy.
• Dòng thứ hai chứa N số nguyên ai, mỗi số cách nhau một dấu cách.
Dữ liệu ra: Kết quả ghi vào file SEQ.OUT:
• Chứa độ dài lớn nhất của dãy con chia hết hoàn toàn tìm được.
Giới hạn: N <= 10000.
-50000<=ai<=50000.
Ai giải giúp với, nếu là quy hoạch động thì chỉ tớ luôn tại sao có công thức truy hồi đó luôn nhá.
Bookmarks