Straightforward Optimization for 3250. Find the Count of Monotonic Pairs I
Intuition\n\nthis is follow-up of leetcode 3250. Find the Count of Monotonic Pairs I.\n\nin leetcode 3250, you\'ll probably come up with O(n*max(nums)*max(nums)
# Intuition\n\nthis is follow-up of [leetcode 3250. Find the Count of Monotonic Pairs I](https://leetcode.com/problems/find-the-count-of-monotonic-pairs-i/).\n\nin leetcode 3250, you\'ll probably come up with `O(n*max(nums)*max(nums))` solution like below:\n\n```py\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        n = len(nums)\n        mod = 10**9 + 7\n        mx = max(nums)\n        \n        dp = [[0]*(mx+1) for _ in range(n)]\n        for num1 in range(mx+1):\n            num2 = nums[0] - num1\n            if num2 >= 0:\n                dp[0][num1] = 1\n            else:\n                break\n\n        for i in range(1, n):\n\n            for num1 in range(nums[i]+1):\n                num2 = nums[i]-num1\n                if num2 < 0: break\n\n                upperbound = min(nums[i-1]-num2, num1)\n                for prev_num1 in range(upperbound+1):\n                    dp[i][num1] += dp[i-1][prev_num1]\n                    dp[i][num1] %= mod\n\n        return sum(dp[n-1]) % mod\n```\n\nit\'s obvious that 3rd for-loop is linear summation which means we can apply **prefix sum** to optimize it.\n\ndefine presum_dp[i][num] = sum(dp[i][0] + dp[i][1] + ... + dp[i][num])\n\nwe can convert 3rd for-loop into:\n\n```py\nupperbound = min(nums[i-1]-num2, num1)\nif upperbound >= 0:\n    dp[i][num1] += presum_dp[i-1][upperbound]\n    dp[i][num1] %= mod\n```\n\nand remember to update **presum_dp**.\n\n# Complexity\n- Time complexity:\n\n    $$O(n * (2*max(nums)))$$\n\n- Space complexity:\n\n    $$O(n * max(nums))$$\n\n# Code\n```py\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        n = len(nums)\n        mod = 10**9 + 7\n        mx = max(nums)\n        \n        dp = [[0]*(mx+1) for _ in range(n)]\n        for num1 in range(mx+1):\n            num2 = nums[0] - num1\n            if num2 >= 0:\n                dp[0][num1] = 1\n            else:\n                break\n\n        presum_dp = [[0]*(mx+1) for _ in range(n)]\n        presum_dp[0][0] = dp[0][0]\n        for num in range(1, mx+1):\n            presum_dp[0][num] = presum_dp[0][num-1] + dp[0][num]\n\n        for i in range(1, n):\n\n            for num1 in range(nums[i]+1):\n                num2 = nums[i]-num1\n                if num2 < 0: break\n\n                upperbound = min(nums[i-1]-num2, num1)\n                if upperbound >= 0:\n                    dp[i][num1] += presum_dp[i-1][upperbound]\n                    dp[i][num1] %= mod\n            \n            presum_dp[i][0] = dp[i][0]\n            for num in range(1, mx+1):\n                presum_dp[i][num] = presum_dp[i][num-1] + dp[i][num]\n\n        return sum(dp[n-1]) % mod\n```
['Python3']