1. //给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 
    2. //
    3. // 一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, 
    4. //i + k)] 包含 两个端点的任意位置。 
    5. //
    6. // 你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。 
    7. //
    8. // 请你返回你能得到的 最大得分 。 
    9. //
    10. // 
    11. //
    12. // 示例 1： 
    13. //
    14. // 
    15. //输入：nums = [1,-1,-2,4,-7,3], k = 2
    16. //输出：7
    17. //解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。
    18. // 
    19. //
    20. // 示例 2： 
    21. //
    22. // 
    23. //输入：nums = [10,-5,-2,4,0,3], k = 3
    24. //输出：17
    25. //解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。
    26. // 
    27. //
    28. // 示例 3： 
    29. //
    30. // 
    31. //输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
    32. //输出：0
    33. // 
    34. //
    35. // 
    36. //
    37. // 提示： 
    38. //
    39. // 
    40. // 1 <= nums.length, k <= 105 
    41. // -104 <= nums[i] <= 104 
    42. // 
    43. // 👍 17 👎 0

    这是220周周赛的第三题，在当时没做出来，脑子里想了多种方式，把自己绕进去了。
    先看题，很显然是个dp，而且是很容易想出来的那种dp。
    再看数据规模，估算一下，暴力dp的话，时间复杂度要到O(nk), 大概率是超时的。于是当时写出代码后也没有提交，在考虑优化。
    首先想到的就是贪心，因为在i位置能够向前找到第一个正数的话，那么一定会经过这个正数。
    但是实际很难编写，因为有可能出现前k步里一个正数都没有都情况。
    再后想到的优化方法就是使用一个数组保存当前位置k步以内的最大分数位置，这个实际上很简单，用优先队列将分数和索引保存即可，但是比赛时并没有想到。
    代码如下：

    2. public int maxResult(int[] nums, int k) {
    3.     // 创建优先队列，用于保存位置i和对应i位置的分数
    4.     // 按照分数的大小排列。
    5.     PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> { return o2[0] - o1[0]; });
    6.     // 0位置的分数就是nums[0]
    7.     queue.offer(new int[]{nums[0], 0});
    8.     int res = nums[0];
    9.     for (int i = 1; i < nums.length; i++) {
    10.         // 如果最大分数距离i位置都距离已经超过k，那么这个位置都分数就已经没有价值了。
    11.         // 将之出队列，使用后面的分数
    12.         while (i - queue.peek()[1] > k){
    13.             queue.poll();
    14.         }
    15.         // 当前位置的得分就是k步以内的最大分数加上当前位置的分数
    16.         res = queue.peek()[0] + nums[i];
    17.         // 将i位置的分数和索引放到优先队列里
    18.         queue.offer(new int[]{res, i});
    19.     }
    20.     // 目标就是最后一步的得分，刚好res到最后一步就截止了
    21.     return res;
    22. }

    比赛时都想到了解决方法，但是并没有想到实际的去使用，还是暴露了题目写少了，而且对优先队列这个数据结构使用不熟练的原因。