DP and prefix sum, O(N*M)
Intuition\n Describe your first thoughts on how to solve this problem. \nI felt like this was some sort of cumulative sum and math problem, so I thought that I\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI felt like this was some sort of cumulative sum and math problem, so I thought that I\'d have to optimize the inner for loop of my problem 3 solution.\n\nI solved problem 3 with the below nested for loops.\n```\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        max_el = max(nums)\n        n = len(nums)\n\n        # n_ways[i][num] = number of ways to make a monotonic pair\n        # where the non-decreasing array ends with num\n        n_ways = [[0 for _ in range(max_el+1)] for _ in range(n)]\n        \n        # populate initial\n        for num in range(nums[0]+1):\n            n_ways[0][num] = 1\n        # dp\n        for i in range(1, n):\n            for num in range(nums[i]+1):\n                total = 0\n                next_nonincreasing = nums[i] - num\n                # the non-decreasing can use any of the items <= num\n                for past_num in range(num+1):\n                    past_nonincreasing = nums[i-1] - past_num\n                    if next_nonincreasing > past_nonincreasing:\n                        continue\n                    else:\n                        # this is a valid continuation\n                        total += n_ways[i-1][past_num]\n                # store the total\n                n_ways[i][num] = total\n\n        for row in n_ways:\n            print(row)\n        return sum(n_ways[-1]) % int(1e9 + 7)\n```\n\nHowever, this would\'ve been too slow. So, I looked at the relationship between `past_num` and `total`. It\'s a lot to write, but basically for any num in which our non-decreasing sequence ends, we want to consider all possible past_nums for which the previous non-decreasing sequence ended. By the constraint that it\'s non-decreasing, `past_num` <= `num`. However, we don\'t want to have to loop through all `num` numbers to figure out which one results in a previous non-increasing subsequence end that would be less than our current non-increasing value. In other words, we want to only consider all `past_num`s for which `nums[i-1] - past_num >= cur_nonincreasing_value`. Upon simplifying, we get `past_num <= nums[i-1] - nums[i] + num`. Thus, we take the minimum of `num` and the above formula to get the index into our cumulative sums that we should use.\n\n# Complexity\nGiven that n is len(nums) and m is max(nums), this solution has the below complexity:\n- Time complexity: $$O(n*m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n*m)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        # for the non-decreasing arr1 to be non-decreasing\n        # its last element must be at most nums[-1]\n        # so all its elements <= nums[-1]\n        max_el = max(nums)\n        n = len(nums)\n\n        # n_ways[i][num] = number of ways to make a monotonic pair\n        # where the non-decreasing array ends with num\n        n_ways = [[0 for _ in range(max_el+1)] for _ in range(n)]\n        \n        # populate initial\n        for num in range(nums[0]+1):\n            n_ways[0][num] = 1\n        # I solved problem 3 with nested for loops \n        # dp with O(n*max^2) <= 2000 * 1000 * 1000 operations\n        # not going to pass\n        # so we need to optimize that inner step\n        for i in range(1, n):\n            # use prefix sum to get the sum for an arbitrary past_num\n            # then, use the observation that\n            # for an arbitrary num, the complement to the non_decreasing number is\n            # the non_increasing number, calculated as non_increasing = nums[i] - num\n            # so since we need the previous non_decreasing to be >= non_increasing\n            # we consider all past_num for which nums[i-1] - past_num >= non_increasing\n            # which means all past_num <= nums[i-1] - non_increasing\n            # which means all past_num <= nums[i-1] - (nums[i] - num)\n            # which means all past_num <= nums[i-1] - nums[i] + num\n            # However, we also know that past_num must be <= num due\n            # to the non-decreasing nature, we know past_num <= num\n            # thus, we can say that past_num <= min(nums[i-1] - nums[i] + num, num)\n            # we use this as our index into our cumulative sums\n            sums = [el for el in n_ways[i-1]]\n            for j in range(1, len(sums)):\n                sums[j] += sums[j-1]  # cumulative sums\n\n            for num in range(0, nums[i]+1):\n                non_increasing = nums[i] - num\n                next_end = nums[i-1] - nums[i] + num\n                if next_end < 0:\n                    continue\n                \n                # since this must be non_decreasing (>=), we need a num >= next_end\n                # print(\'considering\', next_end, \'vs\', num, \'on\', i)\n                next_end= min(next_end, num)\n                n_ways[i][num] = sums[next_end]\n\n        return sum(n_ways[-1]) % int(1e9 + 7)\n```
['Python3']