Python Solution | DP | Optimal Solution
Approach\n Describe your approach to solving the problem. \nIn the first part of this we were updating the dp for ith index for allsatisfying values based on th
# Approach\n<!-- Describe your approach to solving the problem. -->\nIn the first part of this we were updating the dp for `i`th index for allsatisfying values based on the values of index `curIdx - 1`. But we cannot do that here because it would exceed time limit. Upon observation, we see that always a range is updated based on the\nvalue of previous index. We can optimise range updates by using difference array. If we want to update range `[a, b]` with value `c` we add value `c` at index `a` and `-c` at index `b + 1`. Then we take prefix sum to get the original array.\n\n# Complexity\n- Time complexity: $$O(max(nums) * n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1002 * n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python []\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        maxElement, MOD = max(nums), 1000000007\n        dp = [[0] * 1002 for _ in range(len(nums))]\n        for prevIncreasing in range(nums[0] + 1): \n            dp[0][prevIncreasing] = 1\n        for curIdx in range(1, len(nums)):\n            for prevIncreasing in range(nums[curIdx - 1] + 1):\n                if nums[curIdx] < prevIncreasing: break\n                curIncreasing, prevDecreasing = prevIncreasing, nums[curIdx - 1] - prevIncreasing\n                if nums[curIdx] - prevIncreasing > prevDecreasing:\n                    curIncreasing = nums[curIdx] - prevDecreasing\n                dp[curIdx][curIncreasing] += dp[curIdx - 1][prevIncreasing]\n                dp[curIdx][nums[curIdx] + 1] -= dp[curIdx - 1][prevIncreasing]\n            for prevIncreasing in range(1, 1002):\n                dp[curIdx][prevIncreasing] += dp[curIdx][prevIncreasing - 1]\n        return sum(dp[-1]) % MOD\n```
['Array', 'Dynamic Programming', 'Python', 'Python3']