LeetCode.5180 Constrained Subset Sum

1.Problem
https://leetcode.com/contest/weekly-contest-186/problems/constrained-subset-sum/

2.Idea
DP + maxQueue

3.Source

 class MaxQueue {  
 public:  
      MaxQueue() {}  
      bool empty() { return elements.empty(); }  
      int size() { return elements.size(); }  
      void push(int val) {  
           elements.push(val);  
           while (!maxElements.empty() && val > maxElements.back()) maxElements.pop_back();  
           maxElements.push_back(val);  
      }  
      int pop() {  
           int val = elements.front();  
           elements.pop();  
           if (val == maxElements.front()) maxElements.pop_front();  
           return val;  
      }  
      int peekMax() {  
           return maxElements.front();  
      }  
 private:  
      queue<int> elements;  
      deque<int> maxElements;  
 };  
 class Solution {  
 public:  
      int dp[100005];  
      int constrainedSubsetSum(vector<int>& nums, int k) {  
           int n = nums.size();  
           int ans = -1000000007;  
           MaxQueue mq;  
           memset(dp, 0, sizeof dp);  
           dp[0] = nums[0];  
           mq.push(nums[0]);  
           for (int i = 1; i<n; i++) {  
                dp[i] = max(nums[i], mq.peekMax() + nums[i]);  
                ans = max(ans, dp[i]);  
                mq.push(nums[i]);  
                if (mq.size() > k) mq.pop();  
           }  
           return ans;  
      }  
 };