Constrained Subsequence Sum

Given integer array nums and k, return the largest sum of a nonempty subsequence whose consecutive selected indices differ by at most k. Preserve original…

Given integer array nums and k, return the largest sum of a nonempty subsequence whose consecutive selected indices differ by at most k. Preserve original index order; the values need not increase and the elements need not be contiguous. Starting at any index is allowed, but choosing nothing is not.

- 1 <= nums.length <= 100000; -10000 <= nums[i] <= 10000. - 1 <= k <= nums.length; inputs are strict integers, not Booleans or fractions. - Return a signed integer in [-10000,1000000000]. - These implementations retain an explicit length-n DP array and use O(n) auxiliary space. - Teaching traces use at most 12 values; coding retains full bounds.

Example 1: input nums = [10,2,-10,5,20], k = 2; output 37. Indices 0,1,3,4 give sum 37 with consecutive gaps at most 2.

Example 2: input nums = [1,-100,10], k = 2; output 11. Select indices 0 and 2: gap exactly k is allowed, giving 11.

Example 3: input nums = [10,-100,-100,5], k = 2; output 10. The initial 10 cannot precede index 3 directly: that gap is 3. Starting at 5 does not beat 10.

Category: Queues. Topic: queue. Difficulty: Hard. Patterns: linear-scan.