Welcome to Subscribe On Youtube
1696. Jump Game VI
Description
You are given a 0-indexed integer array nums and an integer k.
You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.
You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.
Return the maximum score you can get.
Example 1:
Input: nums = [1,-1,-2,4,-7,3], k = 2 Output: 7 Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.
Example 2:
Input: nums = [10,-5,-2,4,0,3], k = 3 Output: 17 Explanation: You can choose your jumps forming the subsequence [10,4,3] (underlined above). The sum is 17.
Example 3:
Input: nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 Output: 0
Constraints:
1 <= nums.length, k <= 105-104 <= nums[i] <= 104
Solutions
Solution 1: Dynamic Programming + Monotonic Queue Optimization
We define $f[i]$ as the maximum score when reaching index $i$. The value of $f[i]$ can be transferred from $f[j]$, where $j$ satisfies $i - k \leq j \leq i - 1$. Therefore, we can use dynamic programming to solve this problem.
The state transition equation is:
\[f[i] = \max_{j \in [i - k, i - 1]} f[j] + nums[i]\]We can use a monotonic queue to optimize the state transition equation. Specifically, we maintain a monotonically decreasing queue, which stores the index $j$, and the $f[j]$ values corresponding to the indices in the queue are monotonically decreasing. When performing state transition, we only need to take out the index $j$ at the front of the queue to get the maximum value of $f[j]$, and then update the value of $f[i]$ to $f[j] + nums[i]$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.
-
class Solution { public int maxResult(int[] nums, int k) { int n = nums.length; int[] f = new int[n]; Deque<Integer> q = new ArrayDeque<>(); q.offer(0); for (int i = 0; i < n; ++i) { if (i - q.peekFirst() > k) { q.pollFirst(); } f[i] = nums[i] + f[q.peekFirst()]; while (!q.isEmpty() && f[q.peekLast()] <= f[i]) { q.pollLast(); } q.offerLast(i); } return f[n - 1]; } } -
class Solution { public: int maxResult(vector<int>& nums, int k) { int n = nums.size(); int f[n]; f[0] = 0; deque<int> q = {0}; for (int i = 0; i < n; ++i) { if (i - q.front() > k) q.pop_front(); f[i] = nums[i] + f[q.front()]; while (!q.empty() && f[q.back()] <= f[i]) q.pop_back(); q.push_back(i); } return f[n - 1]; } }; -
class Solution: def maxResult(self, nums: List[int], k: int) -> int: n = len(nums) f = [0] * n q = deque([0]) for i in range(n): if i - q[0] > k: q.popleft() f[i] = nums[i] + f[q[0]] while q and f[q[-1]] <= f[i]: q.pop() q.append(i) return f[-1] -
func maxResult(nums []int, k int) int { n := len(nums) f := make([]int, n) q := []int{0} for i, v := range nums { if i-q[0] > k { q = q[1:] } f[i] = v + f[q[0]] for len(q) > 0 && f[q[len(q)-1]] <= f[i] { q = q[:len(q)-1] } q = append(q, i) } return f[n-1] } -
function maxResult(nums: number[], k: number): number { const n = nums.length; const f: number[] = Array(n).fill(0); const q = new Deque<number>(); q.pushBack(0); for (let i = 0; i < n; ++i) { if (i - q.frontValue()! > k) { q.popFront(); } f[i] = nums[i] + f[q.frontValue()!]; while (!q.isEmpty() && f[i] >= f[q.backValue()!]) { q.popBack(); } q.pushBack(i); } return f[n - 1]; } class Node<T> { value: T; next: Node<T> | null; prev: Node<T> | null; constructor(value: T) { this.value = value; this.next = null; this.prev = null; } } class Deque<T> { private front: Node<T> | null; private back: Node<T> | null; private size: number; constructor() { this.front = null; this.back = null; this.size = 0; } pushFront(val: T): void { const newNode = new Node(val); if (this.isEmpty()) { this.front = newNode; this.back = newNode; } else { newNode.next = this.front; this.front!.prev = newNode; this.front = newNode; } this.size++; } pushBack(val: T): void { const newNode = new Node(val); if (this.isEmpty()) { this.front = newNode; this.back = newNode; } else { newNode.prev = this.back; this.back!.next = newNode; this.back = newNode; } this.size++; } popFront(): T | undefined { if (this.isEmpty()) { return undefined; } const value = this.front!.value; this.front = this.front!.next; if (this.front !== null) { this.front.prev = null; } else { this.back = null; } this.size--; return value; } popBack(): T | undefined { if (this.isEmpty()) { return undefined; } const value = this.back!.value; this.back = this.back!.prev; if (this.back !== null) { this.back.next = null; } else { this.front = null; } this.size--; return value; } frontValue(): T | undefined { return this.front?.value; } backValue(): T | undefined { return this.back?.value; } getSize(): number { return this.size; } isEmpty(): boolean { return this.size === 0; } }