vivek_ragi

JUMP_GAMES_6

Jun 11th, 2021
545
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int maxResult(vector<int>& nums, int k) {
  4.         int n = nums.size();
  5.        
  6.         int dp[n];
  7.        
  8.         memset(dp, 0 ,sizeof(n));
  9.        
  10.         dp[0] = nums[0];
  11.         priority_queue<pair<int,int>> pq;
  12.         pq.push({dp[0],0});
  13.         //O(n*logn)
  14.         for(int i = 1; i < n ; ++i)
  15.         {
  16.             while(pq.top().second < i - k)
  17.             {
  18.                 pq.pop();
  19.             }
  20.             dp[i] = nums[i] + pq.top().first;
  21.             pq.push({dp[i],i});
  22.         }
  23.         return dp[n - 1];
  24.     }
  25. };
RAW Paste Data