Quiet window
MediumOnline Assessment
Find the longest stretch of consecutive loads whose total stays within a budget.
Choose a contiguous segment of loads (consecutive entries, in their original order) so that the sum of the chosen entries is at most budget. Return the largest possible number of entries in such a segment. Because every load is non-negative, extending a segment never decreases its sum.
Input: loads, a list of non-negative integers, and budget, a non-negative integer.
Output: an integer, the maximum segment length. If no single load fits (or loads is empty), the empty segment is allowed and the answer is 0.
An O(n) approach exists; inputs are large enough that checking every segment will be too slow.
Example 1
- Input:
- [[2,1,4,1,1],5]
- Output:
- 2
- Explanation
- The segments [2, 1] (sum 3), [1, 4] (sum 5) and [4, 1] (sum 5) fit the budget of 5. Any segment of length 3 sums to 6 or 7, so the answer is 2.
Example 2
- Input:
- [[3,1,2,1,1,4,1,1,1],5]
- Output:
- 4
- Explanation
- The segment [1, 2, 1, 1] has sum 5, which fits, and it has 4 entries. No segment of 5 entries sums to 5 or less, so the answer is 4.
Example 3
- Input:
- [[0,0,0],0]
- Output:
- 3
- Explanation
- Every load is 0, so the whole list sums to 0, which is within a budget of 0. The answer is 3.
Constraints
0 <= loads.length <= 100,0000 <= loads[i] <= 1,0000 <= budget <= 100,000,000