Leetcode3250：单调数组对的数目 I

题目描述：

给你一个长度为 n 的 正 整数数组 nums 。

如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：

• 两个数组的长度都是 n 。
• arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
• arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
• 对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。

请你返回所有 单调 数组对的数目。

由于答案可能很大，请你将它对 109 + 7 取余 后返回。

代码思路：

代码使用了动态规划和前缀和的技巧。以下是代码的详细思路：

代码实现：

const int MOD = 1e9 + 7;
class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        vector<int> acc(nums[0] + 1, 0);
        iota(acc.begin(), acc.end(), 1);

        for (auto&& p = nums.begin() + 1; p != nums.end(); p++) {
            vector<int> temp(*p + 1, 0);
            partial_sum(acc.begin(), acc.begin() + min(*p,p[-1]) + 1, temp.begin() + max(0,*p-p[-1]),
                        [](int sum, int a) { return (sum + a) % MOD; });
            acc = temp;
        }
        return acc.back() ;
    }
};