Dynamic Programming21 sections · 915 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,max⁡j=i−ki−1(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.