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.