瑟瑟發(fā)抖

3妹：好冷啊， 凍得瑟瑟發(fā)抖啦
2哥 : 沒想到都立春了還這么冷啊~
3妹：暴雪、凍雨、大雨，這天氣還讓不讓人活啦！?。?br> 2哥 :哎，好多人都滯留的高鐵站了，沒法回家了
3妹：我還不知道今天怎么回家呢，慘。
2哥：3妹，要不別回去了吧，我們就地過年
3妹：切，這里更冷，每天抖啊抖，跳啊跳才能緩解寒冷，我們家那兒可是有暖氣的。
2哥：好吧，回家也也要記得每天刷題啊，剛好今天的題目是跳躍的， 讓我們先做一下吧~

吃瓜

題目：

給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 和一個整數(shù) k 。

一開始你在下標(biāo) 0 處。每一步，你最多可以往前跳 k 步，但你不能跳出數(shù)組的邊界。也就是說，你可以從下標(biāo) i 跳到 [i + 1， min(n - 1, i + k)] 包含 兩個端點的任意位置。

你的目標(biāo)是到達(dá)數(shù)組最后一個位置（下標(biāo)為 n - 1 ），你的 得分 為經(jīng)過的所有數(shù)字之和。

請你返回你能得到的 最大得分 。

示例 1：

輸入：nums = [1,-1,-2,4,-7,3], k = 2
輸出：7
解釋：你可以選擇子序列 [1,-1,4,3] （上面加粗的數(shù)字），和為 7 。
示例 2：

輸入：nums = [10,-5,-2,4,0,3], k = 3
輸出：17
解釋：你可以選擇子序列 [10,4,3] （上面加粗?jǐn)?shù)字），和為 17 。
示例 3：

輸入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
輸出：0

提示：

1 <= nums.length, k <= 10^5
-10^4 <= nums[i] <= 10^4

思路：

思考

動態(tài)規(guī)劃 + 雙端隊列,
每一個位置的最大值取決于前面 k 步的最大得分，再加上當(dāng)前位置的得分，由此我們想到可以使用動態(tài)規(guī)劃來解決這個問題。

用 dp[i]來表示到達(dá)位置 i 的最大得分。初始狀態(tài) dp[0]=nums[0]，表示位置 0的得分是它本身的得分。狀態(tài)轉(zhuǎn)移方程是

dp[i]=max?{dp[j]}
其中 max?(0,i?k)≤j<i。

其中前 k 步的最大值，使用優(yōu)先隊列可以達(dá)到 O(n×log?n)的時間復(fù)雜度，使用雙端隊列可以達(dá)到 O(n)的時間復(fù)雜度。

java代碼：

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offerLast(0);
        for (int i = 1; i < n; i++) {
            while (queue.peekFirst() < i - k) {
                queue.pollFirst();
            }
            dp[i] = dp[queue.peekFirst()] + nums[i];
            while (!queue.isEmpty() && dp[queue.peekLast()] <= dp[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        return dp[n - 1];
    }
}