aboutsummaryrefslogtreecommitdiff
path: root/jump_game6.cpp
blob: 81bbf050879aeda8ebb629df9c9fbdcd25a9d092 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include "leetcode.h"

class Solution {
public:
  int maxResult(vector<int> &nums, int k) {
    int ans = 0;
    deque<int> dq;
    for (int i = nums.size() - 1; i >= 0; i--) {
      ans = nums[i] + (dq.empty() ? 0 : nums[dq.front()]);
      while (!dq.empty() && ans > nums[dq.back()])
        dq.pop_back();
      dq.push_back(i);
      if (dq.front() >= i + k)
        dq.pop_front();
      nums[i] = ans;
    }
    return ans;
  }
};

int main() {
  Solution obj;
  vector<int> nums = {1, -1, -2, 4, -7, 3};
  int k = 2;
  cout << obj.maxResult(nums, k);
}