All problems

Best Training Block

Hard · sliding window

An athlete scores every training day. You are given a list scores where scores[i] is the score on day i. A bad day can have a negative score.

The coach will pick one block: a run of neighbouring days, with none skipped. The block must be at least lo days long and at most hi days long, both limits included. The total of a block is the sum of its daily scores.

Return the largest total that any allowed block can have. You must pick a block, even if every total is negative, so the answer can be negative.

Examples

Example 1

Input: scores = [3, -2, 5, -1, 2], lo = 2, hi = 3

Output: 6

The blocks [3, -2, 5] and [5, -1, 2] both total 6. No two-day block beats 4, and no other three-day block beats 6.

Example 2

Input: scores = [-4, -1, -3], lo = 1, hi = 2

Output: -1

Every day is bad, so the best choice is the single day with score -1.

Example 3

Input: scores = [4, -10, 6, 2, -1], lo = 3, hi = 5

Output: 7

The block [6, 2, -1] has three days and totals 7. The whole five-day run only totals 1.

Constraints