1499

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<pair<int, int>> q;
        int ans=INT_MIN;
        for(int i=0; i<points.size(); i++){
            int x = points[i][0]; int y = points[i][1];
            // Pop from front until elements are in  x-k range.
            while(!q.empty() && x-k > q.front().second)
                q.pop_front();

            // Update ans.
            if(!q.empty()) ans = max(ans, q.front().first + x + y);

            // Maintain monotonic behavior by having highest (y-x) values at back of queue.
            // This monotonic behaviour avoids use of priority queue.
            while(!q.empty() && q.back().first < y-x)
                q.pop_back();
            q.push_back({y-x, x});
        }
        return ans;
    }
};