Recursive two-pointer / prefix sum 94.82% on Monotonic Pairs II, 99.70% on Monotonic Pairs I
Intuition\n\nIf [$k_1$,$k_2$,...$k_{i-1}$, $k_i$] is a part of a monotonic pair for the first $i$ element prefix array, \n[$k_1$,$k_2$,...$k_{i-1}$] is one for 
# Intuition\n\nIf [$k_1$,$k_2$,...$k_{i-1}$, $k_i$] is a part of a monotonic pair for the first $i$ element prefix array, \n[$k_1$,$k_2$,...$k_{i-1}$] is one for the first $i-1$ element prefix array.\n\nThe count of monotonic pairs will also be the count of pairs ending in $x_1$ + the count ending in $x_2$ + the count ending in $x_3$, etc for each possible ending value.\n\n# Approach\n\nCreate a helper function for finding the counts of monotonic pairs of prefix arrays up to element `end_index` of the first `end_index+1` elements with each ending value.  The range of possible ending values from this helper for the first $n$ elements is limited in the following ways:\n\n1. Since arr1 is monotonically non-decreasing, the min value must be >= the min value for the first $n-1$ element ending values.  It also must be >= 0.\n2. The maximum value must be <= `nums[n - 1]`, aliased as `target` in the code.\n3. Since `arr1[i] + arr2[i] == nums[i]`, the range of arr2 ending values is `[target - a1_max; target - a1_min]`, where a1_min & a1_max are the limits for the a1 ending value described in 1 & 2.  Furthermore, since arr2 is non-increasing, the prior a2_min must be >= target - a1_max, which gives us additional restriction on a1_max, and since a1 = target - a2, with a2 <= previous a2, a1 >= target - previous_a2, so calculating the prior a2 range gives us additional restriction on a1.\n\nTo save space, we store the list of counts as an offset and a vector, where `offset` = the minimum possible ending value, so each vector element `counts[i]` represents the # of possible monotonic pairs where the $arr1$ ending element is `offset + i`.\n\nWe loop through each possible ending value in the range `[a1_min; a1_max]`, calculating the values that are acceptable for the end of the previous prefix array for that value, and from there offsets into the previous `CountsByEnd`.  In order to avoid needing to loop adding up the entire subset of the vector for each ending value, we keep track of a prefix sum (`sum`), and the range that was already added, adjusting that range to the new range by adding or subtracting values from the ends.  This range should really never vary by more than 1 element from 1 ending value to the next.  \n\n\n# Complexity\n- Time complexity:\nO($nR$), where $n$ is the size of the arrays and $R$ is the size of the range of values for each array element.  I believe for working out the `arr1[k]` end value counts, $R$ ends up being 1 + the minimum element of the first k + 1 elements of `nums`.  Automatic analysis incorrectly identifies this as O($n^2$).\n\n- Space complexity:\nO(`nums[0] + min(nums[0], nums[1])`)\n\nAt any point during this algorithm, the size of the working array will be the size of the minimum value seen in `nums` so far, and we need the previous working array still around.  This can only shrink after the first 2 elements, and despite being recursive, the previous recursive call has returned before the new working `CountsByEnd` is constructed.\n\n# Code\n```cpp []\nauto fast = (ios::sync_with_stdio(0), cout.tie(0), cin.tie(0), false);\nconstexpr int kMod = 1000000007;\nstruct CountsByEnd {\n    int offset;\n    vector<int> counts;\n};\nCountsByEnd kEmptyCounts{.offset = 0};\nstruct Solution {\n    CountsByEnd helper(const vector<int>& nums, int end_index) {\n        if (end_index == 0) {\n            return CountsByEnd{.offset = 0,\n                               .counts = vector<int>(nums.front() + 1, 1)};\n        }\n        CountsByEnd pc = helper(nums, end_index - 1);\n        const auto& pc_vec = pc.counts;\n        if (pc.counts.empty())\n            return pc;\n        int target = nums[end_index], pt = nums[end_index - 1],\n            pamn = pc.offset, pamx = pamn + (int)pc_vec.size() - 1,\n            pa2mn = pt - pamx,\n            a1_min = max(max(0, pamn), target - min(pt - pamn + 1, pt - pamn));\n        if (target < a1_min) {\n            return kEmptyCounts;\n        }\n        CountsByEnd ans{\n            .offset = a1_min,\n        };\n        auto& ans_counts = ans.counts;\n        ans_counts.reserve(target - a1_min + 1);\n        int prior_included_a1_begin = 0, pr_end_offset = 0;\n        int64_t sum = 0;\n        for (int a1 = a1_min; a1 <= target; ++a1) {\n            int pa1max = min(min(a1, pamx), pt - max(target - a1, pa2mn)),\n                end_offset = min(pa1max + 1 - pamn, (int)pc_vec.size());\n            while (pr_end_offset < end_offset)\n                sum += pc_vec[pr_end_offset++];\n            while (pr_end_offset > end_offset)\n                sum -= pc_vec[--pr_end_offset];\n            while (sum >= kMod)\n                sum -= kMod;\n            ans_counts.push_back(sum);\n        }\n        return ans;\n    }\n    int countOfPairs(vector<int>& nums) {\n        int64_t ans = 0;\n        CountsByEnd cbe = helper(nums, nums.size() - 1);\n        return std::accumulate(cbe.counts.begin(), cbe.counts.end(), 0LL) %\n               kMod;\n    }\n};\n\n```
['Two Pointers', 'Dynamic Programming', 'Recursion', 'Prefix Sum', 'C++']