Longest dry stretch within a rainfall budget
A vineyard logs the rainfall of every day in millimetres. The manager wants the longest stretch of consecutive days whose combined rainfall does not exceed a budget B, because that is how long the ground stays workable. Print the length of the longest such stretch. If every single day on its own already exceeds B, print 0.
Input
The first line holds N and B separated by a space: the number of days (1 to 100000) and the budget (0 to 1000000000). The second line holds N non-negative integers, the daily rainfall in millimetres (0 to 1000000).
Output
One line: the maximum number of consecutive days whose rainfall sums to at most B.
Example 1
Input
7 10 3 4 2 6 1 0 5
Output
4
Days 3 to 6 give 2 + 6 + 1 + 0 = 9, which fits the budget of 10. No five consecutive days fit.
Example 2
Input
5 3 4 4 4 4 4
Output
0
Every day alone is over budget, so no stretch qualifies.
Example 3
Input
6 5 0 0 0 0 0 0
Output
6
Six dry days sum to 0, so the whole log qualifies.
Constraints
- 1 <= N <= 100000
- 0 <= B <= 1000000000
- 0 <= rainfall <= 1000000
- A solution that checks every pair of start and end days is too slow for the largest inputs
Hints
Hint 1 of 3
Checking every start and end pair is O(N^2). Because rainfall is never negative, a window's sum only grows when you extend it to the right and only shrinks when you drop days from the left.
Hint 2 of 3
Keep two indexes, $left and $right, and a running $sum. Move $right one day at a time; while $sum exceeds the budget, subtract $rain[$left] and move $left forward.
Hint 3 of 3
After the while loop the window $left..$right is valid (possibly empty when $left > $right); its length is $right - $left + 1, and you keep the largest seen.
Solution
Show a reference solution and explanation
<?php
[$n, $budget] = array_map('intval', explode(' ', trim(fgets(STDIN))));
$rain = array_map('intval', explode(' ', trim(fgets(STDIN))));
$best = 0;
$sum = 0;
$left = 0;
for ($right = 0; $right < $n; $right++) {
$sum += $rain[$right];
while ($sum > $budget && $left <= $right) {
$sum -= $rain[$left];
$left++;
}
$length = $right - $left + 1;
if ($length > $best) {
$best = $length;
}
}
echo $best, "\n";
Why it works
This is a sliding window, sometimes called two pointers. The key property is that all values are non-negative: adding a day never lowers the sum and removing a day never raises it, so a window that is over budget can only be fixed by dropping days from its left end. Each day is added once and removed at most once, which makes the whole scan O(N) even though there is a loop inside a loop. The tricky edge case is a single day that exceeds the budget on its own: the inner loop then moves $left past $right, the window length becomes 0, and the answer stays 0 if that happens for every day. The starter reads the input with array_map('intval', explode(...)), which is the standard way to turn a line of numbers into an integer array.
Lesson for this exercise: Arrays in PHP