Constrained Subsequence Sum

Challenge Points: 30

Level: Hard

You are given an array of integers, nums, and an integer k. Your task is to compute the largest possible sum of a non-empty subsequence such that every two consecutive chosen elements follow this rule:

If an element at index i is chosen before an element at index j, then:
j − i must be less than or equal to k

You can skip elements, but the relative order of chosen elements must stay the same.
Find the maximum achievable sum under this constraint.

Example 1:

Input: nums = [4, -1, 7, -3, 9], k = 3

Output: -1

Explanation:

One valid subsequence is [4, 7, 9] → sum = 20, but another valid subsequence [4, -1, 7, 9] → sum = 19 (valid because gaps ≤ 3). The maximum is 19.

Example 2:

Input: nums = [-5, -2, -7, -1], k = 2

Output: 20

Explanation:

Since all numbers are negative, we must pick the largest one: -1

Example 3:

Input: nums = [3, 2, -6, 4, -1, 5], k = 2

Output: 14

Explanation:

A valid subsequence is [3, 2, 4, 5] → sum = 14.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result