难度: Medium
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
示例 1：
输入：nums = [1,-1,-2,4,-7,3], k = 2 输出：7 解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。
示例 2：
输入：nums = [10,-5,-2,4,0,3], k = 3 输出：17 解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。
示例 3：
输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 输出：0
提示：
1 <= nums.length, k <= 105-104 <= nums[i] <= 104运行时间: 88 ms
内存: 27.5 MB
class Solution:
def maxResult(self, nums: List[int], k: int) -> int:
if k == 1:
return sum(nums)
ans = nums[0]
lastPositiveIdx = 0
n = len(nums)
for i in range(1, len(nums)):
if nums[i] >= 0 or i == n - 1:
# we encountered a negative list we can't jump over
if i - lastPositiveIdx - 1 >= k:
# we use dp to solve this local problem
# dp[j] = nums[j] + max([dp[i] for i in range(j-k, j)])
# but k may be a large number, it's not efficient
# since we only rely on the max on in the range
# we can use a decreasing mono queue to speed up
# we just put the dp[i] result in this mono queue
# and we can get the max one quickly
nums[lastPositiveIdx] = 0
monoQueue = collections.deque([lastPositiveIdx])
for j in range(lastPositiveIdx+1, i+1):
if j - monoQueue[0] > k:
monoQueue.popleft()
nums[j] += nums[monoQueue[0]]
while monoQueue and nums[monoQueue[-1]] <= nums[j]:
monoQueue.pop()
monoQueue.append(j)
ans += nums[i]
lastPositiveIdx = i
return ans
这道题的核心思路是使用动态规划(DP)结合单调队列优化。DP数组表示到达每个位置i的最大得分。为了避免重复计算每个位置最大得分时所有可能的前驱位置的得分，我们使用一个单调队列来优化这个过程。队列中存储的是索引，且保证队头是最大的DP值的索引。遍历数组时，每到一个正数或者数组最后一个元素，检查是否能直接从上一个正数位置跳到当前位置。如果不能，就用单调队列来计算从上一个正数位置到当前位置的最大得分，更新中间的DP值，并更新队列以保持单调递减。总的来说，此题解通过减少重复计算并快速访问当前最大得分，从而降低了时间复杂度。
时间复杂度: O(n)
空间复杂度: O(k)
class Solution:
def maxResult(self, nums: List[int], k: int) -> int:
if k == 1:
return sum(nums) # 当k=1时，直接返回整个数组的和
ans = nums[0] # 初始化答案为第一个元素的值
lastPositiveIdx = 0 # 记录上一个非负数的索引
n = len(nums)
for i in range(1, len(nums)):
if nums[i] >= 0 or i == n - 1: # 当前数为非负数或者到达数组最后
if i - lastPositiveIdx - 1 >= k: # 如果无法直接跳到当前位置
nums[lastPositiveIdx] = 0 # 将上一个正数位置置0，因为我们不会从它开始
monoQueue = collections.deque([lastPositiveIdx]) # 初始化单调队列，从上一个正数位置开始
for j in range(lastPositiveIdx+1, i+1):
if j - monoQueue[0] > k:
monoQueue.popleft() # 如果队首元素距离大于k，弹出队首
nums[j] += nums[monoQueue[0]] # 更新当前位置的得分为队首的最大得分加上当前数
while monoQueue and nums[monoQueue[-1]] <= nums[j]:
monoQueue.pop() # 维持队列的单调递减性
monoQueue.append(j) # 将当前索引加入队尾
ans += nums[i] # 更新答案
lastPositiveIdx = i # 更新上一个正数的位置
return ans # 返回最终的最大得分
题解在此处的确简化了问题处理。实际上，当`k=1`时，由于每一步只能向前移动一位，因此无论正负，你都必须走过数组中的每一个数。因此直接求和是正确的，因为你不能跳过任何元素，包括负数。这种方法并没有真正忽略负数的影响，而是反映了每步都必须经过的情况，即使这些步骤中包含负数。
单调队列是按照值的单调递减顺序来维持元素的。在算法中，每当添加一个新的元素到单调队列时，会从队尾开始比较，把所有小于等于当前元素值的索引从队尾移除。这样做确保了队列里剩下的都是比当前元素大的值，且队头是所有这些元素中最大的。当超出跳跃范围`k`时，队首元素会被移除。这样，队头始终是在允许跳跃范围内的最大DP值的索引。
这里并不是忽略了负数，而是对策略进行了优化。题解中的策略是在遇到非负数或数组最后一个元素时，尝试直接跳跃，如果不行（即两者之间的间隔超过了k），则使用单调队列来计算最优路径。这种做法是为了减少计算复杂度，因为非负数自然会增加得分，优先从这些点跳跃可能直接获得更高的分数。在不能直接跳跃的情况下，通过单调队列处理保证了即使存在负数，也能计算到最优解。