Max Reward Trajectory With Bounded Step Gap
A reinforcement-learning rollout has per-step rewards. You select an increasing subsequence of steps where consecutive picks are at most k apart, maximizing total reward — modeling a policy that may skip but not stall.
Problem
Given an integer array rewards and an integer k, choose a non-empty subsequence such that for every pair of consecutive chosen indices i < j we have j - i <= k. Maximize the sum of chosen rewards. Return that maximum. Rewards may be negative; a single element is a valid subsequence.
Input
An integer array rewards and an integer k (the maximum index gap).
Output
An integer: the maximum achievable subsequence sum.
Constraints
- 1 <= rewards.length <= 10^5
- -10^4 <= rewards[i] <= 10^4
- 1 <= k <= rewards.length
Examples
Example 1
Input
rewards = [10,2,-10,5,20], k = 2
Output
37
Pick indices 0,1,3,4 (gaps <= 2): 10 + 2 + 5 + 20 = 37.
Example 2
Input
rewards = [-1,-2,-3], k = 1
Output
-1
All negative; the best is the single largest element -1.