Total of Unit-Step Chains

Hard

Call a sequence of numbers a **chain** if every number is exactly 1 more than the one before it, or every number is exactly 1 less than the one before it. The direction never changes within a chain: [3, 4, 5] and [9, 8] are chains, while [3, 4, 3] and [8, 6] are not. A single number is a chain too. You get an array values. Consider all of its non-empty subsequences (elements taken in their original order, not necessarily adjacent) that are chains. Subsequences taken from different positions count separately, even if they hold the same numbers. Return the sum of the elements of all such subsequences, modulo 10⁹ + 7.

Example 1

values=[3, 4, 3] → 24

The chains are [3], [4], [3], [3, 4] and [4, 3]. Their sums add up to 3 + 4 + 3 + 7 + 7 = 24.

Example 2

values=[5, 5, 6] → 38

The single elements give 16, and the chain [5, 6] can be picked in two ways (with either 5), adding 2 · 11 = 22. The total is 38.

Example 3

values=[2, 1, 3, 2] → 24

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Dynamic Programming

Similar problems

Every Way to Space the Words Hard Square-Sum Chains Hard Split With a Repeat Penalty Hard Roots That Fit the Guesses Hard Climbing Along Rows and Columns Hard

Input

values=[3, 4, 3]

Expected

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