A free-runner crosses a row of rooftops numbered 0 to n - 1. Landing on roof i earns bonus[i] points (negative bonuses are penalties). She starts on roof 0, which counts its bonus, and must finish on roof n - 1. Every leap goes forward and covers at least near and at most far roofs: from roof i she can land on roofs i + near to i + far.
Return the largest total bonus of a run that ends on roof n - 1, or None if the last roof cannot be reached at all. With a single roof the answer is bonus[0].
Examples
Input: bonus = [2, -8, 3, -1, 5], near = 1, far = 2
Output: 10
Explanation: roofs 0 -> 2 -> 4.
Input: bonus = [4, 9, 1, 6], near = 2, far = 3
Output: 10
Explanation: roof 1 can never be reached; leap 0 -> 3.
Input: bonus = [1, 1, 1, 1, 1], near = 3, far = 3
Output: None
Constraints
1 <= len(bonus) <= 10**5,-10**4 <= bonus[i] <= 10**41 <= near <= far <= 10**5- Target complexity: O(n). With a wide range of leap lengths, checking every earlier roof is too slow.
Goals
- Write a max-dp whose window of predecessors lags behind the current index
- Insert a predecessor into the deque only when it becomes far enough behind
- Keep unreachable positions out of the dp without breaking the window