Maximum Sum With Short Hops

Hard

You are given an integer array values and an integer max_hop. Pick a non-empty set of elements so that any two neighboring picks (in array order) have indices at most max_hop apart. In other words, if indices i < j are picked and nothing between them is, then j - i ≤ max_hop. Return the largest possible sum of the picked elements.

Example 1

values=[4, -7, 3, -1, -2, 6], max_hop=2 → 12

Take 4, 3, -1 and 6: the picked indices 0, 2, 3, 5 are never more than 2 apart. The sum is 12.

Example 2

values=[-5, -2, -8], max_hop=3 → -2

Every number is negative and an empty pick is not allowed, so take just -2.

Example 3

values=[9, -20, -20, 9], max_hop=2 → 9

Constraints

1 ≤ max_hop ≤ len(values) ≤ 10⁵
-10⁴ ≤ values[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Queue Array Dynamic Programming Sliding Window Monotonic Queue Heap (Priority Queue)

Similar problems

Moving Window Maximum Hard A Dark Gap Between Street Lamps Hard Shortest Stretch Reaching a Total Hard Best Pair of Close Beacons Hard Ferry Runs From the Depot Hard

Input

values=[4, -7, 3, -1, -2, 6], max_hop=2

Expected

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