703. The Longest Stretch Inside a Budget
Find the longest contiguous stretch whose total is at most k. Print its length, or 0
when even a single value exceeds k.
2 1 5 1 3 2, k = 8 -> 3 the stretch 2 1 5 totals exactly 8
1 1 1 1, k = 2 -> 2
10 20, k = 5 -> 0
## The mirror of problem 681
681 asks for the SHORTEST stretch reaching a target from below. This asks for the LONGEST staying under a ceiling. Both rest on the same property: the values are positive, so the total rises as the window grows and falls as it shrinks.
Where 681 records a length while the window is still legal and then shrinks, this shrinks first and records afterwards. Which side of the shrink the recording goes on is the whole difference, and getting it backwards is the usual bug.
## The sweep
for hi in 0 .. n-1:
s += a[hi]
while s > k and lo <= hi:
s -= a[lo]; lo += 1
best = max(best, hi - lo + 1)
## The empty window
A single value larger than k empties the window: lo passes hi, the length becomes 0, and
the answer stays 0 unless something later fits. The lo <= hi guard is what stops the left
pointer running past the right one.
10 20 with k = 5 is that case, and an unguarded loop reads outside the array.
## Why positivity matters, again
With a zero or a negative value the total no longer rises with the window, the shrink loop can overshoot, and the method stops being correct. Problems 689, 694 and 675 depend on the same promise, and each says so.
When the values CAN be negative the window fails outright and the shortest-reaching-a-target version needs prefix sums with a monotonic deque, which is problem 706.
## Overflow
200000 values up to 10^4 total 2 * 10^9, and k can be that large too.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 10^9` - `1 ≤ each value ≤ 10^4`
Input
The first line contains two integers n and k.
The second line contains n positive integers.
Output
Print one integer, the length of the longest stretch totalling at most k.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.