Dãy con liên tiếp dài nhất có tổng không vượt quá S
Xem dạng PDF
Gửi bài giải
Điểm:
12,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho dãy số ~a~ có ~N~ phần từ nguyên ~a_1, a_2,...,a_N~ và một số nguyên ~S~ bất kì. Một dãy con liên tiếp của dãy số a có dạng ~a_i, a_{i+1},...,a_j~ với ~ 1 \le i \le j \le N~ tổng của dãy con liên tiếp bằng ~a_i+ a_{i+1}+...+a_j~, độ dài của dãy con liên tiếp bằng ~j - i +1 ~.
Yêu cầu: Tìm dãy con liên tiếp của dãy số ~a~ có độ dài lớn nhất và có tổng không lớn hơn ~S~?
Dữ liệu vào:
- Dòng 1: ghi 2 số nguyên ~N~ và ~S~ (~N \le 10^6, S \le 10^9~)
- Dòng 2: ghi lần lượt các số nguyên không âm ~a_1, a_2,...,a_N~,(~a_i \le 10^6, i = 1..N~).
Dữ liệu ra:
- Gồm một số duy nhất là độ dài của dãy con liên tiếp dài nhất thoả mãn.
Ví dụ:
Input:
8 7
6 8 2 4 5 1 9 3
Output:
2
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.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
cũng có thể áp dùng 2 pointer:()