Use dynamic programming.

Let dp[i] be the solution for the prefix of the array that ends at index i, if the element at index i is in the subsequence.

dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])

Use a heap with the sliding window technique to optimize the dp.