One Forgiven Day
gains[i] is what a shop earned on day i, and it may be negative. Pick a stretch of consecutive days, then erase at most one day from it, as long as at least one day of the stretch remains.
Return the largest possible total of the days that remain.
Example 1
gains [3,-8,4,5]
returns 12
Take all four days and erase the -8: 3 + 4 + 5 = 12.
Example 2
gains [-5,-2,-7]
returns -2
Every day loses money, so keep the single day -2. Erasing it would leave nothing.
Constraints
1 <= len(gains) <= 100-1000 <= gains[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Paint the FenceMedium
- Shared Subsequence LengthMedium
- Trading With Rest DaysMedium
- Unique Binary Search TreesMedium
- Unique Grid PathsMedium
- Ways to Make ChangeMedium
- At Most K TradesHard
- Cheapest Order of CutsHard