Subsequences With an Even Step

Hard

You are given an integer array values. Count its subsequences that have at least three elements and in which every two neighbouring elements differ by the same amount. A subsequence is what remains after crossing out some elements of the array (possibly none) while keeping the rest in order. Subsequences built from different positions count separately, even if their values are the same. For example, [9, 6, 3] and [2, 2, 2, 2] fit, while [1, 2, 4] does not.

Example 1

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

The fitting ones are [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4].

Example 2

values=[5, 5, 5, 5] → 5

With a step of 0 every subsequence fits: four ways to choose three positions and one way to choose all four.

Example 3

values=[3, 1, -1, 4, -3] → 3

Constraints

1 ≤ len(values) ≤ 1000
-2³¹ ≤ values[i] ≤ 2³¹ − 1
The answer does not exceed 2³¹ − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Water Between Walls Hard Biggest Solid Panel Block Hard Profit From Two Trades Hard Every Way to Space the Words Hard Crossing the Cave Hard

Input

values=[1, 2, 3, 4]

Expected

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