Constrained Subsequence Sum

Hard

Given an integer array nums and an integer target (= k), return the maximum sum of a non-empty subsequence such that for every two consecutive chosen elements at indices i < j, the condition j - i <= target holds.

Example 1

Input:  nums = [10,2,-10,5,20], target = 2
Output: 37

Example 2

Input:  nums = [-1,-2,-3], target = 1
Output: -1

Example 3

Input:  nums = [10,-2,-10,-5,20], target = 2
Output: 23

Constraints

• 1 <= target <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4