Best Score With Jumps of at Most K

You get an integer array nums and an integer k.

You start at index 0 and you must finish at the last index. In one jump you move forward by 1 to k steps. You may not jump past the last index.

Your score is the sum of nums[i] for every index i you land on, including index 0 and the last index. Return the largest score you can get.

If nums has one element, you are already at the end, and the score is nums[0].

Hint

Let best[i] be the largest score for a path that ends at index i. Then best[i] = nums[i] + the largest of best[i - k] to best[i - 1]. Computing that largest value directly costs O(k) per index. A deque of indices whose best values go down from front to back gives it in O(1), so the whole solution is O(n).