# [LeetCode 1696. Jump Game VI ](https://leetcode.com/explore/challenge/card/june-leetcoding-challenge-2021/604/week-2-june-8th-june-14th/3773/)
### Daily challenge Jun 9, 2021 (MEDAIN)

>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.

:::info
**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.
:::

:::info
**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.
:::

:::info
**Example 3:**
**Input:** nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
**Output:** 0
:::

:::warning
**Constraints:**
* 1 <= nums.length, k <= 105
* -104 <= nums[i] <= 104
:::

---

### Approach 1 : DP + Deque :book:
**`152 ms ( 89.83% )`** **`O(N)`**

:::success
* **deque** 是 C++ 標準模板函式庫（Standard Template Library, STL）中的雙向佇列容器（**Double-ended Queue**），跟 vector 相似，不過在 vector 中若是要添加新元素至開端，其時間複雜度為 `O(N)`，但在 deque 中則是 `O(1)`。同樣地，也能在我們需要儲存更多元素的時候自動擴展空間，讓我們不必煩惱佇列長度的問題。
* deque 實際上仍然是使用`連續記憶體空間`實作而成的，並不是雙向的 linked list。


* 優點 :
1. 可以再兩端進行 push 和 pop 操作。
2. 支持隨機訪問[i]。
* 缺點 :
1. 佔用記憶體較多。
:::

* 一次最多可以走 `k` 步，所以當我們在 `i` 時，我們會希望從 `i-k ~ i-1` 找到`最大值`，最後加上 `nums[i]`。
因為 `k` 不是固定的，如果每次都要從 `i-k ~ i-1` 找到最大值，會非常浪費時間。
* 使用 **`deque`** 紀錄 `前 k 個`最大值所在的 **`index`**---> **`deque.front()`** 即最大值。
* 當 `index = i` 時，
>1. 若 **`i - deque.front() > k`**，則將它 `pop_front` ( 表示無法走到 `i` )。
>2. 更新 **`dp[i] = nums[i] + dp[deque.front()]`**。
>3. 從`尾端`開始判斷，若 **`dp[i] > dp[deque.back()]`**，可以直接 `pop_back`。
( `i > deque.back() && dp[i] > dp[deque.back()]`，表示在之後的 `steps` 中，`i` 的結果都會比較好 )。
>4. 最後再將 **`dp[i]`** 放入 `deque` 尾端。

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int size = nums.size();
        deque<int > max_index;
        vector<int > dp(size, INT_MIN);

        dp[0] = nums[0];
        max_index.push_back(0);
        
        for(int i=1; i<size; i++){
            // pop_front(), if i - front() > k // 
            if(i - max_index.front() > k)   max_index.pop_front();
            
            // dp //
            dp[i] = nums[i] + dp[max_index.front()];
            
            // pop_back(), if dp[back()] < dp[i] --> means it will not be a good answer //
            while(!max_index.empty() && dp[i] > dp[max_index.back()]){
                max_index.pop_back();
            }
            max_index.push_back(i);
        }
        
        return dp[size-1];
    }
};