leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1696.cpp (460B)

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