All problems

Longest Spending Spell

Hard · prefix sum

Tomas tracks his money. The list spend holds his net spending for each day, in order. A day with a refund can have a negative number, because he got money back.

A spell is one or more days in a row, with none skipped. The cost of a spell is the sum of the net spending of its days. Tomas wants to find a spell that stays within his budget, which means its cost is at most budget. The budget can be negative: then the spell must have earned money back overall.

Return the number of days in the longest spell whose cost is at most budget. If no spell fits, return 0.

Examples

Example 1

Input: spend = [6, -2, -3, 8, 1], budget = 1

Output: 3

Days 1 to 3 cost 6 - 2 - 3 = 1, which fits. No spell of four or five days costs 1 or less.

Example 2

Input: spend = [5, 6, 7], budget = 4

Output: 0

Every single day already costs more than 4.

Example 3

Input: spend = [4, -3, 5, -6, 2], budget = 3

Output: 5

All five days cost 2 together, which fits.

Constraints