hardDynamic Programming 1DAI-applied~30 min
Maximum Reward Across Generation Steps
A decoding policy moves through generation steps; from step i it may advance 1..k steps. Each step carries a signed reward. Maximize total reward collected from the first step to the last.
Problem
Given an integer array reward (which may contain negatives) and an integer k, start at index 0 and end at index n-1. From index i you may jump to any index in [i+1, i+k] that is within bounds. Return the maximum sum of reward values over the indices you land on, including index 0 and index n-1.
Input
An integer array reward and an integer k.
Output
An integer: the maximum achievable total reward.
Constraints
- 1 <= reward.length <= 100000
- 1 <= k <= reward.length
- -10000 <= reward[i] <= 10000
Examples
Example 1
Input
reward = [1,-1,-2,4,-7,3], k = 2
Output
7
Path 0 -> 1 -> 3 -> 5 collects 1 + (-1) + 4 + 3 = 7.
Example 2
Input
reward = [10,-5,-2,4,0,3], k = 3
Output
17
Path 0 -> 3 -> 5 collects 10 + 4 + 3 = 17.