Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 1696 Jump Game VI - Problem Statement

LeetCode 1696

You're at index 0 of an array nums. From index ii, you can jump to any index jj where i<ji+ki < j \leq i + k. Your score is the sum of all visited elements. Find the maximum score to reach the last index.

Example: nums = [1, -1, -2, 4, -7, 3], k = 2. One optimal path: 0 → 2 → 4 → 5 with score 1+(2)+(7)+3=51 + (-2) + (-7) + 3 = -5. Wait, that's not right. Let me reconsider: 0 → 1 → 3 → 5 with score 1+(1)+4+3=71 + (-1) + 4 + 3 = 7. This is where DP meets monotonic queues. The naive DP is O(nk)O(nk). Can you see the sliding window structure?