2022-07-09

很经典的一道题，用到的一个小技巧可以积累，就是对一个子数组进行动态优先队列的构建，用值和下标构建pair插入优先队列，每次调用最值前，弹出窗口范围外的元素，很经典，值得学习和积累

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        
        int n = nums.size();
        if(n==1)
            return nums[0];
        if(n==2)
            return nums[0]+nums[1];
        vector<int> dp(n, INT_MIN/2);
        dp[n-1] = nums[n-1];
        int b = n-1;
        int a = n-1-k;
        priority_queue<pair<int,int>, vector<pair<int,int>>>pq;
        pq.push({nums[n-1], b});
        int sum = nums[0]+nums[n-1];
        for(int i=b-1; i>a && i>=0; i--){
            dp[i] = pq.top().first + nums[i];
            pq.push({dp[i], i});
            if(i>0 && nums[i]>0)
                sum += nums[i];
        }
        if(k>=n)
            return sum;
        for(int i=a; i>=0; i--){
            while(pq.size() && pq.top().second>i+k)
                pq.pop();
            dp[i] = pq.size()? pq.top().first:0;
            dp[i] += nums[i];

            pq.push({dp[i],i});
        }

        return dp[0];
    }
};