A workshop plans one worker's shifts over n hours. Working hour i produces output[i] pieces. Safety rules say the worker may work at most k consecutive hours; any longer streak must be broken by at least one hour off. Return the largest total output a valid plan can achieve.
Examples
Input: output = [5, 3, 4, 8, 1], k = 2
Output: 17
Explanation: rest in hour 2 and work the rest: 5 + 3 + 8 + 1.
Input: output = [2, 7, 1], k = 3
Output: 10
Explanation: three hours in a row are allowed, so no rest is needed.
Constraints
1 <= len(output) <= 10**50 <= output[i] <= 10**41 <= k <= len(output)- Target complexity: O(n) time; an O(n * k) table is too slow when k is large.
Goals
- Rephrase 'take as much as possible' as 'skip as cheaply as possible'
- Express the skip cost with a recurrence over a window of k + 1 positions
- Speed up the window minimum with a monotonic deque