leetcode刷题笔记5631题 删除子数组的最大得分
问题描述：
给你一个下标从 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
import "container/list"
func maxResult(nums []int, k int) int {
length := len(nums)
dp := make([]int, length)
queue := list.New()
dp[0] = 0
queue.PushBack(0)
//滑动窗口内使用单调队列，使得区间内最大值的时间复杂度为O(1)
for i := 0; i < length; i++ {
for (queue.Front().Value.(int) < i - k) {queue.Remove(queue.Front())}
dp[i] = dp[queue.Front().Value.(int)] + nums[i]
for (queue.Len() > 0 && dp[queue.Back().Value.(int)] <= dp[i]) {queue.Remove(queue.Back())}
queue.PushBack(i)
}
return dp[length-1]
}