Loading problem...
You are given an integer array nums and a positive integer k representing the maximum allowed gap between any two consecutively selected elements in a subsequence.
Your task is to find the maximum possible sum of a non-empty subsequence of the array such that for every pair of adjacent elements in the chosen subsequence (elements at positions i and j in the original array where i < j), the positional difference satisfies the constraint: j - i ≤ k.
A subsequence is a sequence derived from the original array by removing zero or more elements while preserving the relative order of the remaining elements. In a valid bounded gap subsequence, no two consecutively chosen elements can be more than k positions apart in the original array.
Since the subsequence must be non-empty, if all elements are negative, you must still select at least one element (the maximum single element would be optimal in such cases).
nums = [10,2,-10,5,20]
k = 237One optimal subsequence is [10, 2, 5, 20]. The indices in the original array are [0, 1, 3, 4]. The gaps between consecutive chosen elements are: 1-0=1, 3-1=2, 4-3=1, all of which are ≤ 2. The sum is 10 + 2 + 5 + 20 = 37.
nums = [-1,-2,-3]
k = 1-1When all elements are negative, we must still select at least one element (the subsequence must be non-empty). The optimal choice is to select only the maximum element, which is -1. Any subsequence with more elements would have a smaller (more negative) sum.
nums = [10,-2,-10,-5,20]
k = 223The optimal subsequence is [10, -2, -5, 20] at indices [0, 1, 3, 4]. The gaps are: 1-0=1, 3-1=2, 4-3=1, all satisfying the constraint j-i ≤ 2. The sum is 10 + (-2) + (-5) + 20 = 23. Note that we include some negative numbers because skipping them entirely would violate the gap constraint (index 0 to index 4 directly has gap 4 > 2).
Constraints