Rising Chain With Small Steps

Hard

You are given an array values and an integer max_step. Pick some elements, keeping their original order, so that the picked values strictly increase and each one exceeds the previous by at most max_step. Return the largest number of elements such a chain can have. A single element counts as a chain.

Example 1

values=[3, 1, 6, 4, 2, 5, 9], max_step=2 → 3

The chain 3, 4, 5 rises in steps of 1, length 3. Something like 1, 2, 5 fails because 5 − 2 = 3 > 2. No chain longer than three exists.

Example 2

values=[2, 2, 2], max_step=5 → 1

Values must strictly increase, so only one of the equal numbers can be used.

Example 3

values=[1, 10, 2, 20, 3], max_step=1 → 3

Constraints

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

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Queue Array Divide and Conquer Dynamic Programming Monotonic Queue

Similar problems

A Dark Gap Between Street Lamps Hard Ferry Runs From the Depot Hard Best Run on a Ring Medium City Block Outline Hard Smaller Values to the Right Hard

Input

values=[3, 1, 6, 4, 2, 5, 9], max_step=2

Expected

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