3796. Find Maximum Value in a Constrained Sequence

You are given an integer n, a 2D integer array restrictions, and an integer array diff of length n - 1. Your task is to construct a sequence of length n, denoted by a[0], a[1], ..., a[n - 1], such that it satisfies the following conditions:

• a[0] is 0.
• All elements in the sequence are non-negative.
• For every index i (0 <= i <= n - 2), abs(a[i] - a[i + 1]) <= diff[i].
• For each restrictions[i] = [idx, maxVal], the value at position idx in the sequence must not exceed maxVal (i.e., a[idx] <= maxVal).

Your goal is to construct a valid sequence that maximizes the largest value within the sequence while satisfying all the above conditions.

Return an integer denoting the largest value present in such an optimal sequence.

class Solution {
public:
    int findMaxVal(int n, vector<vector<int>>& restrictions, vector<int>& diff) {
        vector<int> lim(n,INT_MAX);
        for(auto& r : restrictions) lim[r[0]] = min(lim[r[0]], r[1]);
        lim[0] = 0;
        priority_queue<pair<int,int>,vector<pair<int,int>>, greater<>> q;
        for(int i = 0; i < n; i++) q.push({lim[i], i});
        while(q.size()) {
            auto [val, idx] = q.top(); q.pop();
            if(lim[idx] != val) continue;
            if(idx) {
                int ma = lim[idx] + diff[idx-1];
                if(lim[idx-1] > ma) {
                    lim[idx-1] = ma;
                    q.push({lim[idx-1],idx-1});
                }
            }
            if(idx + 1 < n) {
                int ma = lim[idx] + diff[idx];
                if(lim[idx+1] > ma) {
                    lim[idx+1] = ma;
                    q.push({lim[idx+1],idx+1});
                }
            }
        }
        return *max_element(begin(lim), end(lim));
    }
};