Blocks Raised to Their Peak

Medium

You get an array of non-negative numbers values and a number max_len. Split the array into contiguous blocks, each at most max_len long. Then, in every block, replace all elements with that block's maximum. Return the largest possible sum of the array after this replacement.

Example 1

values=[3, 8, 1, 2, 6], max_len=2 → 31

The blocks [3, 8], [1], [2, 6] become [8, 8], [1], [6, 6], for a sum of 29. Nothing does better.

Example 2

values=[4, 0, 0, 0], max_len=4 → 16

One block over the whole array: four 4s, sum 16.

Example 3

values=[5, 1, 5], max_len=1 → 11

Constraints

1 ≤ len(values) ≤ 500
0 ≤ values[i] ≤ 10⁹
1 ≤ max_len ≤ len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

values=[3, 8, 1, 2, 6], max_len=2

Expected

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