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
cũng có thể áp dùng 2 pointer:()