3251. Find the Count of Monotonic Pairs II

You are given an array of positive integers nums of length n.

We call a pair of non-negative integer arrays (arr1, arr2) monotonic if:

• The lengths of both arrays are n.
• arr1 is monotonically non-decreasing, in other words, arr1[0] <= arr1[1] <= ... <= arr1[n - 1].
• arr2 is monotonically non-increasing, in other words, arr2[0] >= arr2[1] >= ... >= arr2[n - 1].
• arr1[i] + arr2[i] == nums[i] for all 0 <= i <= n - 1.

Return the count of monotonic pairs.

Since the answer may be very large, return it modulo 109 + 7.

class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        long long mod = 1e9 + 7, n = nums.size();
        vector<long long> dp(1001);
        for(int i = 0; i <= nums[0]; i++) dp[i] = 1;
        for(int i = 1; i < n; i++) {
            vector<long long> dpp(1001);
            long long pre = 0;
            queue<pair<int,int>> q;
            for(int j = 0; j <= nums[i]; j++) {
                int k = nums[i] - j, pk = nums[i-1] - j;
                q.push({pk,j});
                while(q.size() and q.front().first >= k) {
                    auto [_,pj] = q.front(); q.pop();
                    pre = (pre + dp[pj]) % mod;
                }
                dpp[j] = pre;
            }
            swap(dp,dpp);
        }
        long long res = 0;
        for(int i = 0; i <= 1000; i++) res = (res + dp[i]) % mod;
        return res;
    }
};