find-the-count-of-monotonic-pairs-ii

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array of positive integers <code>nums</code> of length <code>n</code>.

We call a pair of non-negative integer arrays <code>(arr1, arr2)</code> monotonic if:

<ul>
	<li>The lengths of both arrays are <code>n</code>.</li>
	<li><code>arr1</code> is monotonically non-decreasing, in other words, <code>arr1[0] &lt;= arr1[1] &lt;= ... &lt;= arr1[n - 1]</code>.</li>
	<li><code>arr2</code> is monotonically non-increasing, in other words, <code>arr2[0] &gt;= arr2[1] &gt;= ... &gt;= arr2[n - 1]</code>.</li>
	<li><code>arr1[i] + arr2[i] == nums[i]</code> for all <code>0 &lt;= i &lt;= n - 1</code>.</li>
</ul>

Return the count of monotonic pairs.

Since the answer may be very large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [2,3,2]

Output: 4

Explanation:

The good pairs are:

<ol>
	<li><code>([0, 1, 1], [2, 2, 1])</code></li>
	<li><code>([0, 1, 2], [2, 2, 0])</code></li>
	<li><code>([0, 2, 2], [2, 1, 0])</code></li>
	<li><code>([1, 2, 2], [1, 1, 0])</code></li>
</ol>
</div>

Example 2:

<div class="example-block">
Input: nums = [5,5,5,5]

Output: 126
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 2000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>
</ul>

countOfPairs

Find the Count of Monotonic Pairs II

Array

Math

Dynamic Programming

Combinatorics

Prefix Sum

给你一个长度为&nbsp;<code>n</code>&nbsp;的&nbsp;正&nbsp;整数数组&nbsp;<code>nums</code>&nbsp;。

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

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

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

由于答案可能很大，请你将它对&nbsp;<code>109 + 7</code>&nbsp;取余&nbsp;后返回。

&nbsp;

示例 1：

<div class="example-block">
输入：nums = [2,3,2]

输出：4

解释：

单调数组对包括：

<ol>
	<li><code>([0, 1, 1], [2, 2, 1])</code></li>
	<li><code>([0, 1, 2], [2, 2, 0])</code></li>
	<li><code>([0, 2, 2], [2, 1, 0])</code></li>
	<li><code>([1, 2, 2], [1, 1, 0])</code></li>
</ol>
</div>

示例 2：

<div class="example-block">
输入：nums = [5,5,5,5]

输出：126
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 2000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>
</ul>