FastPrep

Description

Solutions

Submission

Array Break

There is an integer array arr of length n. Two arrays b and c are called a perfect break of arr if:

The lengths of arrays b and c are n.

Elements in array b are in non-decreasing order.

Elements in array c are in non-increasing order.

They satisfy b[i] ≥ 0, c[i] ≥ 0, and b[i] + c[i] = arr[i], for each i where 0 ≤ i < n.

Find the number of possible perfect breaks of arr. Since the number can be large, return the value modulo 1000000007, i.e., (10^9+7).

Function Description

Complete the function perfectBreak in the editor.

perfectBreak has the following parameter:

int arr[n]: the num of possible perfect breaks modulo (10⁹ + 7).

Example 1:

Input:  arr = [2, 3, 2]
Output: 4 
Explanation:
There are 4 possible perfect breaks of array arr:
    
b = [0, 1, 1], c = [2, 2, 1] is a perfect break because it
  - b and c have 3 elements
  - b is non-decreasing order
  - c is in non-increasing order
  - elements of b and c are 0 or more than the sums of a[i] + b[i] = [2, 3, 2], which matches arr.

b = [0, 1, 2], c = [2, 2, 0] is a perfect break.

b = [0, 2, 2], c = [2, 1, 0] is a perfect break.

b = [1, 2, 2], c = [1, 1, 0] is a perfect break.
    
b = [1, 3, 2], c = [1, 0, 0] is not a perfect break because b is not non-decreasing.
      
b = [1, 2, 2], c = [2, 1, 0] is not a perfect break because b[0] + c[0] ≠ arr[0].

Example 2:

Input:  arr = [3, 2]
Output: 6 
Explanation:
The perfect breaks are:

b = [0, 0], c = [3, 2]

b = [0, 1], c = [3, 1]

b = [0, 2], c = [3, 0]

b = [1, 1], c = [2, 1]

b = [1, 2], c = [2, 0]

b = [2, 2], c = [1, 0]

Constraints:

1 <= n <= 3000

1 <= arr[i] <= 3000