Python Prefix Sum DP - O(n*m) (optimized from O(n*m^2) TLE)
SCROLL DOWN FOR PREFIX SUM SOLUTION - BUILDS UP FROM TLE\n# Slow Solution (TLE) - works for Count of Monotonic Pairs I\npython\nclass Solution:\n    def countOf
**SCROLL DOWN FOR PREFIX SUM SOLUTION - BUILDS UP FROM TLE**\n# Slow Solution (TLE) - works for Count of Monotonic Pairs I\n```python\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        m = max(nums)\n        dp = [[0 for _ in range(m+1)] for a in range(len(nums))]\n        for i in range(nums[0]+1):\n            dp[0][i] = 1\n        for i in range(1, len(nums)):\n            for j in range(nums[i]+1):\n                for k in range(0, j + min(nums[i-1] - nums[i], 0) + 1):\n                    dp[i][j] += dp[i-1][k]\n        return sum(dp[-1]) % 1000000007\n```\n## Explanation\nThe DP array has 2 dimensions - the first dimension is the index in `nums`, and the second dimension is the value being considered for placement in `arr1` (the monotonically increasing array).\n\n`dp[i][j]` needs to store the number of distinct arrays which `arr1[:i+1]` could be if only `nums[:i+1]` was being considered, if `arr1[-1] == j` (the last element is `j`)\n\nNote that `arr1` must be monotonically increasing, `arr2` must be montonically decreasing, and `arr2[i] = nums[i] - arr1[i]` as stated by the problem. Therefore, we only need 2 dimensions in the DP rather than 3 since we can calculate `arr2[i]` given `arr1[i]` and `nums[i]`.\n\nWe initialize the array by noting that the value of `arr1[0]` cannot exceed `nums[0]`, since then `nums2[0]` would have to be negative. Since there is only one element in `arr1[:1]`, we set all elements `arr1[0:nums[0]+1] = 1` since there is exactly one distinct subarray of `arr1` which could end with each of those values.\n\nTo implement the recurrence relation, see that `arr1[i] >= arr1[i-1]` must hold, and `arr2[i] == (nums[i]-arr1[i]) <= (nums[i-1]-arr1[i-1]) == arr2[i-1]` must also hold because `arr2[i] = nums[i] - arr1[i]`. Solving the inequality, for every `j`, we only consider values for the previous element in `arr1` ranging from `0` to `j + min(nums[i-1] - nums[i], 0)` to maintain both monotonicity properties. It also must hold that the value for the previous element must be less than or equal to `j` because otherwise `arr1` would not be monotonically increasing.\n\nWcan update each `dp[i][j] = sum([dp[i-1][j] for j in range(j + min(nums[i-1] - nums[i], 0)])` by looping through these elements of `dp`. We use `min` to make sure that the previous element being considered doesn\'t exceed `j`.\n\nNow, the number of possibilities is simply the sum of the last row in `dp`: the number of possibilities for `arr1` ending at each possible value.\n\n\n\n\n\n\n\n<img src="https://assets.leetcode.com/users/images/53ea3db4-c053-40c0-b972-0bd8b4129bfc_1723356427.4958727.png" alt="space" width="200"/>\n\n\n# **Prefix Sums for Optimization**\n```python\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        dp = [[0 for _ in range(max(nums)+1)] if a > 0 else [i+1 if i <= nums[0] else 0 for i in range(max(nums)+1)] for a in range(len(nums))]\n        for i in range(1, len(nums)):\n            s = 0\n            for j in range(nums[i]+1):\n                s += dp[i-1][j + min(nums[i-1] - nums[i], 0)]\n                dp[i][j] = s\n        return max(dp[-1]) % 1000000007\n```\n\n## **Explanation**\n\nNote that, in the inefficient solution, we are using a for loop to sum a contiguous subarray of `dp[i-1]` when updating the elements in `dp[i]`. \n\nWe can replace this with a prefix sum to get the sum of a contiguous range in `O(1)` time and the same memory.\n\nStore each `dp[i]` as a prefix sum rather than an array of elements, and now we can find the sum up to the required value by indexing the prefix sum array (and the range always starts at 0).\n\nThe rest of the solution is exactly the same.
['Dynamic Programming', 'Prefix Sum', 'Python']