leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1696.cpp (460B)

0 class Solution { 1 public: 2 int maxResult(vector<int> &nums, int k) { 3 vector<int> dp(size(nums)); 4 dp[0] = nums[0]; 5 deque<int> q{0}; 6 for (int i = 1; i < size(nums); i++) { 7 if (q.front() < i - k) q.pop_front(); 8 dp[i] = nums[i] + dp[q.front()]; 9 while (!q.empty() && dp[q.back()] <= dp[i]) 10 q.pop_back(); 11 q.push_back(i); 12 } 13 return dp.back(); 14 } 15 };