One Vector DP - Prefix Sum
Intuition\nSince the pairs are dependent on each other and [nums], you can simply search for the # of valid monotonic increasing arrays, and only count the ones
# Intuition\nSince the pairs are dependent on each other and [nums], you can simply search for the # of valid monotonic increasing arrays, and only count the ones that satisfy the monotonically decreasing pair.\n\nFor the monotonic increasing array, if a number n is valid for the pairing, then all values in [0, n-1] are valid previous entries.\n\n# Approach\nCalculate a suffix min, which represents an upper bound for valid monotonic arrays at that digit.\nCreate a DP to store # of valid pairs in previous digit.\nDP is a prefix sum (since all prior values will satisfy the same condition).\n\n# Complexity\n![image.png](https://assets.leetcode.com/users/images/3fc232aa-b11d-4d74-b065-45803b2d2d58_1723371460.0766976.png)\n\n- Time complexity:\nO(n*m), n = nums.size(), m = range of nums[i]\n\n- Space complexity:\nO(N+2*M)\n\n# Code\n```\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums) {\n        const int MOD = 1e9+7;\n        int n = *max_element(nums.begin(), nums.end());\n        vector<int> prev(n+1, 0);\n        \n        prev[0] = 1;\n        for (int i = 1; i <= n; i++) {\n            if (i <= nums[0]) prev[i] = prev[i-1] + 1;\n            else break;\n        }\n        \n        vector<int> suffix(nums.size(), INT_MAX);\n        suffix.back() = nums.back();\n        for (int i = nums.size()-2; i >= 0; i--) {\n            suffix[i] = min(suffix[i+1], nums[i]);\n        }\n\n        int min = 0;\n        for (int i = 1; i < nums.size(); i++) {\n            vector<int> temp(n+1, 0);\n            int a = nums[i-1] - nums[i] + min;\n            if (min < a) a = min;\n            for (int j = min; j <= suffix[i]; j++) {\n                if (j != min) temp[j] = temp[j-1];\n                if (a >= 0) temp[j] += prev[a];\n                if (temp[j] >= MOD) temp[j] -= MOD;\n                a++;\n            }\n\n            // prevent adding hundreds of 0\'s\n            for (int j = min; j <= n; j++) {\n                if (temp[j]) break;\n                min++;\n            }\n            \n            prev = temp;\n        }\n        return prev[suffix.back()];\n    }\n};\n```
['Dynamic Programming', 'Prefix Sum', 'C++']