Dynamic Programming21 sections · 916 units
Open in Course

Constrained Sum - DP Formulation

The twist

Let dp[i]dp[i] = maximum sum of a valid subsequence ending at index ii (must include nums[i]nums[i]). The transition: dp[i]=nums[i]+max(0,maxj=iki1(dp[j]))dp[i] = nums[i] + \max(0, \max_{j=i-k}^{i-1}(dp[j])). You take the best previous subsequence sum if it's positive, otherwise start fresh. The max(0,...)\max(0, ...) is what separates this from Jump Game VI.

If all previous subsequences ending in the window have negative sum, you're better off starting a new subsequence at ii.