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);
}
|