1696. Jump Game VI #

Problem #

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 <= 10^5
• 10^4 <= nums[i] <= 10^4

Problem Statement #

You are given a 0-indexed integer array nums and an integer k. Initially, you are at index 0. In each step, you can jump forward at most k steps, but you cannot jump outside the boundaries of the array. That is, you can jump from index i to any position in [i + 1, min(n - 1, i + k)], inclusive of both endpoints. Your goal is to reach the last position of the array (index n - 1), and your score is the sum of all numbers you pass through. Return the maximum score you can get.

Solution Approach #

• The first approach that comes to mind is dynamic programming. Define dp[i] as the maximum score obtainable by jumping to the i-th position. The problem asks for dp[n-1], and the state transition equation is: dp[i] = nums[i] + max(dp[j]), max(0, i - k ) <= j < i. Note here the lower bound of j: the problem states that you cannot jump into negative-index territory, so the left boundary lower bound is 0. To compute max(dp[j]), you need to traverse once to find the maximum value, so the overall time complexity of this solution is O((n - k) * k). However, after submitting it, it results in a time limit exceeded error.
• Let’s analyze the reason for the timeout. Each time, we need to scan the interval [max(0, i - k ), i) to find the maximum value. The interval in the next round is [max(0, i - k + 1), i + 1). These two consecutive scanned intervals have a large overlapping part, [max(0, i - k + 1), i), and it is precisely the repeated scanning of this part that makes the algorithm inefficient. How to efficiently find the maximum value in an interval is the key to this problem. A monotonic queue can be used to solve it. The monotonic queue stores the index of the maximum value within an interval. Here, the monotonic queue has 2 properties. First, the front of the queue is always the maximum value, and the queue is arranged in descending order from large to small. If an index with a value larger than the front arrives, the monotonic queue needs to be cleared and only this new maximum index stored. Second, the length of the queue is k. New values are inserted from the back, and the maximum value at the front is “pushed” out of the front. With this monotonic queue, the DP state transition becomes very efficient. Each time, you only need to take the maximum value at the front of the queue. See the code below for details.

Code #

package leetcode

import (
	"math"
)

// Monotonic queue
func maxResult(nums []int, k int) int {
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	for i := 1; i < len(dp); i++ {
		dp[i] = math.MinInt32
	}
	window := make([]int, k)
	for i := 1; i < len(nums); i++ {
		dp[i] = nums[i] + dp[window[0]]
		for len(window) > 0 && dp[window[len(window)-1]] <= dp[i] {
			window = window[:len(window)-1]
		}
		for len(window) > 0 && i-k >= window[0] {
			window = window[1:]
		}
		window = append(window, i)
	}
	return dp[len(nums)-1]
}

// Time Limit Exceeded
func maxResult1(nums []int, k int) int {
	dp := make([]int, len(nums))
	if k > len(nums) {
		k = len(nums)
	}
	dp[0] = nums[0]
	for i := 1; i < len(dp); i++ {
		dp[i] = math.MinInt32
	}
	for i := 1; i < len(nums); i++ {
		left, tmp := max(0, i-k), math.MinInt32
		for j := left; j < i; j++ {
			tmp = max(tmp, dp[j])
		}
		dp[i] = nums[i] + tmp
	}
	return dp[len(nums)-1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}