DP + Prefix Sum || Explained
Explanation\n\nSuppose, we are making pairs of the form (arr1[i],arr2[i])\n\nlets say, we are at index = i\nIf we put (x,nums[i]-x) at i\'th index, \nnow questi
# Explanation\n```\nSuppose, we are making pairs of the form (arr1[i],arr2[i])\n\nlets say, we are at index = i\nIf we put (x,nums[i]-x) at i\'th index, \nnow question is \nQ1) What pairs of type (y,nums[i-1]-y) we have have on (i-1)th index?\nQ2) What is the relation between x and y?\n\nAnswer to question 2 is\n" y <= x "    ......... (1) //(because arr1 is non-decreasing)\nnums[i-1]-y >= nums[i]-x   //(because arr2 is non-increasing)\n => nums[i-1] - nums[i] + x >= y\n => " y <= nums[i-1] - nums[i] + x "  ........(2)\n\non combining eq(1) and eq(2), we get\ny <= min(x, nums[i-1] - nums[i] + x)\nwhere (y >= 0 as all integers should be non-negative is given).\n```\n \n# Approach\n```\nFor all indices, {\n    try all values of "x" {\n        for each "x", {\n            add contribution of all "y" \n            satisfying above mentioned equation\n        }\n    }\n}\n\nBonus-\nUse Prefix-Sum for optimization\n```\n\n# Complexity\n- Time complexity: $$O(n*max(nums))$$ \n\n- Space complexity: $$O(max(nums))$$\n\n# Code\n```\n#define mod 1000000007\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums) {\n        if(nums.size() == 1) return nums[0]+1;\n        vector<long long> dp(1001,1);\n        \n        for(int i=1; i<dp.size(); i++) {\n            dp[i] += dp[i-1];\n        }\n\n        for(int i=1; i<nums.size(); i++) {\n            vector<long long> curr(1001,0);\n            for(int x=0; x<=nums[i]; x++) {\n                int y = min(x,nums[i-1] - nums[i] + x);\n                if(y >= 0) curr[x] = (curr[x] + dp[y]) % mod;\n            }\n            for(int i=1; i<curr.size(); i++) {\n                 curr[i] = (curr[i] + curr[i-1]) % mod;\n            }\n         dp = curr;\n        }\n     return dp.back();\n    }\n};\n```
['Dynamic Programming', 'Prefix Sum', 'C++']