Split Into a Climb and a Descent

Hard

You are given an array of positive integers totals of length n. Split every element into two non-negative integer parts: totals[i] = up[i] + down[i]. A split is valid when up never decreases (up[0] ≤ up[1] ≤ … ≤ up[n-1]) and down never increases (down[0] ≥ down[1] ≥ … ≥ down[n-1]). How many valid splits are there? Two splits are different if their up arrays differ. The count can be huge, so return it modulo 10⁹ + 7.

Example 1

totals=[3, 1] → 3

Three splits work: up=[0, 0], down=[3, 1]; up=[0, 1], down=[3, 0]; up=[1, 1], down=[2, 0].

Example 2

totals=[4, 4, 4] → 35

Here up can be any non-decreasing triple of numbers from 0 to 4, and down then comes out non-increasing on its own. There are 35 such triples.

Example 3

totals=[1, 5, 1] → 0

The jump from 1 to 5 forces up to grow by at least 4, yet its last element can be at most 1. No split exists.

Constraints

1 ≤ len(totals) ≤ 2000
1 ≤ totals[i] ≤ 50

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Dynamic Programming Combinatorics Prefix Sum

Similar problems

Split Into a Climb and a Descent: Large Values Hard A Fair Split of Colored Beads Hard Other Orders for the Same Search Tree Hard K-th Route in Alphabetical Order Hard Merge the Front Tiles Hard

Input

totals=[3, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.