Find the Count of Monotonic Pairs I

This approach optimizes the naive DP solution by observing that the inner loop is calculating a sum over a range. Such summations can be computed efficiently using prefix sums. By pre-calculating the prefix sums for each row of the DP table, we can determine the value of any dp[i][j] in constant time, which significantly improves the overall time complexity.

• The DP state dp[i][j] is the same as the naive approach.
• The transition dp[i][j] = sum(dp[i-1][k]) is over a contiguous range of k.
• The upper bound for k is limit = min(nums[i-1], j - max(0, nums[i] - nums[i-1])).
• We can precompute prefix sums for each row i-1 of the DP table into an array ps[i-1].
• dp[i][j] can then be found in O(1) time using ps[i-1][limit].
• This removes the innermost loop from the naive DP approach.

The key insight is that the transition dp[i][j] = sum(dp[i-1][k]) is performed for k in the range [0, limit], where limit = min(nums[i-1], j - max(0, nums[i] - nums[i-1])). This is a prefix sum.

We can maintain a parallel 2D array, ps, where ps[i][x] stores the sum of dp[i][k] for k from 0 to x. After computing the i-1-th row of the dp table, we can compute the i-1-th row of the ps table in O(M) time. Then, when computing the i-th row of dp, each dp[i][j] can be found in O(1) by looking up the precomputed value in ps[i-1], effectively eliminating one loop from the previous approach.

Algorithm Steps:

1. Create a DP table dp[n][M+1] and a prefix sum table ps[n][M+1].
2. Base Case (i=0): Fill dp[0] and ps[0] as before.
3. Transitions (i > 0): For i from 1 to n-1:
   • For each j from 0 to nums[i]:
     • Calculate the upper bound for k: limit = min(nums[i-1], j - max(0, nums[i] - nums[i-1])).
     • If limit >= 0, set dp[i][j] = ps[i-1][limit].
   • Compute the prefix sums for the new dp[i] row and store them in ps[i].
4. Final Result: The answer is ps[n-1][nums[n-1]].

class Solution {
    public int countMonotonicPairs(int[] nums) {
        int n = nums.length;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }
        long[][] dp = new long[n][maxVal + 1];
        long[][] ps = new long[n][maxVal + 1];
        int MOD = 1_000_000_007;

        // Base case: i = 0
        for (int j = 0; j <= nums[0]; j++) {
            dp[0][j] = 1;
        }
        ps[0][0] = dp[0][0];
        for (int j = 1; j <= maxVal; j++) {
            ps[0][j] = (ps[0][j - 1] + dp[0][j]) % MOD;
        }

        // Fill DP table for i > 0
        for (int i = 1; i < n; i++) {
            long diff = (long)nums[i] - nums[i-1];
            for (int j = 0; j <= nums[i]; j++) {
                long k_upper_bound = j - Math.max(0, diff);
                long limit = Math.min(nums[i-1], k_upper_bound);
                
                if (limit >= 0) {
                    dp[i][j] = ps[i-1][(int)limit];
                }
            }
            
            ps[i][0] = dp[i][0];
            for (int j = 1; j <= maxVal; j++) {
                ps[i][j] = (ps[i][j - 1] + dp[i][j]) % MOD;
            }
        }

        return (int) ps[n - 1][nums[n - 1]];
    }
}