Longest affordable stretch
A hiking app splits a trail into consecutive segments and records the climb of each segment in metres (never negative). A walker sets a climb budget and wants to know the longest stretch of consecutive segments they can walk without the combined climb going over that budget.
Read the budget and the segment climbs and print the maximum number of consecutive segments whose total climb is at most the budget. If even a single segment exceeds the budget everywhere, the answer is 0.
Input
Two lines. The first is an integer budget B. The second has n integers separated by single spaces, the climb of each segment in order.
Output
One line: the largest number of consecutive segments whose climbs sum to at most B.
Example 1
Input
10 3 4 2 5 1 6
Output
3
Segments 3, 4, 2 sum to 9 and segments 2, 5, 1 sum to 8. No run of four fits within 10, so the answer is 3.
Example 2
Input
4 7 9
Output
0
Both segments alone are over budget, so no stretch at all is affordable.
Constraints
- 0 <= B <= 1000000000
- 1 <= n <= 5000
- 0 <= each climb <= 1000000
- Aim for a single pass over the segments
Hints
Hint 1 of 3
Checking every possible start and end pair works but does more work than needed; because climbs are never negative, a window that is over budget only gets worse when it grows.
Hint 2 of 3
Keep two indexes, left and right, and the sum of the segments between them. Move right forward one step at a time, adding to the sum.
Hint 3 of 3
Whenever the sum goes over the budget, move left forward, subtracting what leaves the window, until it fits again. After that the window right - left + 1 is the longest one ending at right.
Solution
Show a reference solution and explanation
int budget = int.Parse(Console.ReadLine()!);
int[] climb = Console.ReadLine()!.Split(' ').Select(int.Parse).ToArray();
int best = 0;
int left = 0;
long sum = 0;
for (int right = 0; right < climb.Length; right++)
{
sum += climb[right];
while (sum > budget)
{
sum -= climb[left];
left++;
}
best = Math.Max(best, right - left + 1);
}
Console.WriteLine(best);
Why it works
The sliding window works because the climbs are non-negative: extending a window can only raise its sum, and shrinking it from the left can only lower it. So for each right there is a unique smallest left that keeps the window affordable, and that left never has to move backwards as right advances. Each index enters and leaves the window at most once, giving a single pass over the array instead of a nested loop. The awkward case is a segment larger than the whole budget: the inner while then pushes left past right, the window becomes empty with length 0, and the algorithm carries on correctly. Using a long for the sum guards against overflow when both the values and the budget are near their limits.