KTLT 14. Đầu tư chứng khoán
Harry làm việc ở một công ty tư vấn đầu tư chứng khoán. Nhiệm vụ của Harry là phân tích sự giao động chỉ số chứng khoán hàng ngày của sàn giao dịch, từ đó có thể các thông tin hữu ích để tư vấn cho các nhà đầu tư.
Nhiệm vụ của Harry trong đề án đang thực hiện là như sau: Cho dãy chỉ số chứng khoán của n ngày liên tiếp. Cần phải tìm ra dãy con dài nhất sao cho chênh lệch hai chỉ số liên tiếp không ít hơn k. Ví dụ, với dãy chỉ số chứng khoán 1014, 1024, 1034, 1045, 1030, 998 và k = 15 thì dãy con 1014, 1034, 998 là chấp nhận được, nhưng dãy 1014, 1045,1030, 998 là dãy con dài nhất cần tìm.
Yêu cầu: Cho n, k và dãy các chỉ số chứng khoán (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10^9). Các chỉ số chứng khoán là những số nguyên dương, có giá trị không vượt quá 109. Hãy chỉ ra dãy con dài nhất thỏa mãn các điều kiện đã nêu.
Dữ liệu: Vào từ file văn bản FINANCIAL.INP
• Dòng đầu tiên chứa hai số nguyên n và k,
• Dòng thứ 2 chứa n số nguyên – các chỉ số chứng khoán.
Kết quả: Đưa ra file văn bản FINANCIAL.OUT:
• Dòng đầu tiên đưa ra độ dài của dãy con tìm được,
• Dòng thứ hai – các chỉ số thuộc dãy con theo trình tự xuất hiện.
Nếu có nhiều dãy con cùng độ dài thì đưa ra dãy tùy ý.
Ví dụ:
FINANCIAL.INP
6 15
1014 1024 1034 1045 1030 998
FINANCIAL.OUT
4
1014 1045 1030 998