470. Blocks Scored by Their Largest

Cut the array into consecutive blocks, each of length at most k. A block of length L whose largest element is m scores L * m. Print the largest total score over all ways of cutting.

1 15 7 9 2 5 10, k = 3 -> 84

That cut is [1 15 7] [9] [2 5 10], scoring 3*15 + 1*9 + 3*10 = 45 + 9 + 30 = 84.

The scoring rewards putting a large element beside small ones, because the large element is then paid for the whole block. 9 1 1 1 with k = 2 answers 20, from [9 1] [1 1] scoring 18 + 2, rather than 12 from [9] [1] [1] [1].

## The recurrence

Every cut ends somewhere, so think about where the LAST block starts:

dp[0] = 0 dp[i] = max over L in 1..min(k, i) of dp[i-L] + L * max(a[i-L .. i-1])

dp[i] is the best score for the first i elements. The inner loop walks the last block backwards, and the maximum of that block is maintained as it grows, so the whole thing is O(n k) with no nested scan for the maximum:

for i in 1..n: m = 0 for L in 1..min(k, i): m = max(m, a[i-L]) dp[i] = max(dp[i], dp[i-L] + L * m)

Growing the block leftward one element at a time and updating m as you go is the detail that keeps this linear in k rather than quadratic. Recomputing max(a[i-L..i-1]) from scratch for each L gives O(n k^2), which is correct and slower.

## What to check

k = 1 forces every element into its own block, so the answer is the plain sum. That is the test 1 2 with k = 1 answering 3, against 4 when k = 2.

k may exceed the remaining length, which is what min(k, i) is for. 1 1 1 9 with k = 4 answers 36, one block of four scored by the 9, and an unclamped loop reads before the start of the array.

Scores reach n times the largest value, so use 64 bits.

Constraints - `1 ≤ n ≤ 20000` - `1 ≤ k ≤ 100` - `0 ≤ value ≤ 10000`