Problem Statement

Given an array arr containing integers and an integer k, return the maximum sum of a non-empty subsequence of arr array such that for every two adjacent integers in the subsequence, arr[i] and arr[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of the array is obtained by removing some elements (may be zero) from the array, leaving the remaining elements in their original order.

Examples

Example 1:

• Input: arr = [10, -2, -10, 5], k = 2
• Expected Output: 13
• Explanation: The subsequence [10, -2, 5] has a maximum sum 13, which follows the given rules.

Example 2:

• Input: arr = [3, 2, 1, -5], k = 1
• Expected Output: 6
• Explanation: The subsequence [3, 2, 1] has a maximum sum, which follows the given rules.

Example 3:

• Input: arr = [3, 2, 7, -5, 10], k = 2
• Expected Output: 22
• Explanation: The optimal subsequence to choose is [3, 2, 7, 10]. Starting with 3, then pick 2 and 7, and finally, skip -5(negative number) and pick 10, resulting in the maximum sum of 22.

Try it yourself

Try solving this question here: