All problems

Boardwalk Pop-Ups

Medium · dynamic programming

A seaside boardwalk has n empty pitches in a row, numbered from 0. If you open a pop-up stall on pitch i, it earns profits[i] for the day.

The council has a crowding rule: any two stalls you open must be at least gap pitches apart. In other words, if you open stalls on pitches i and j, then |i - j| >= gap.

Return the largest total profit you can earn. You may open as many stalls as the rule allows, including none.

Examples

Example 1

Input: profits = [4, 1, 6, 3], gap = 2

Output: 10

Open pitches 0 and 2 for 4 + 6. Pitches 1 and 3 would earn only 1 + 3.

Example 2

Input: profits = [4, 1, 6, 3], gap = 3

Output: 7

Only pitches 0 and 3 are far enough apart (3 pitches), earning 4 + 3. Opening the single best pitch gives just 6.

Example 3

Input: profits = [5], gap = 4

Output: 5

With one pitch there is nothing to clash with.

Constraints