Partition Array for Maximum Sum

Split arr into contiguous, nonempty groups, each containing at most k elements. Replace every value in each group with the largest original value in that group. Return the greatest total sum obtainable after these replacements.

The inputs are chosen so that the maximum sum fits in a signed 32-bit integer.

Example 1:

Input: arr = [2,6,1,4]
k = 2

Output: 20

Explanation: Use groups [2,6] and [1,4]. They become [6,6] and [4,4], giving 20. No other allowed partition produces a larger sum.

Example 2:

Input: arr = [3,1,5]
k = 1

Output: 9

Explanation: With k = 1, every group has one element. No value changes, so the sum is 3 + 1 + 5 = 9.

Example 3:

Input: arr = [0,0]
k = 2

Output: 0

Explanation: All original values are zero. Every possible group still has maximum zero, so the final sum is zero.

Constraints:

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 1000000000
• 1 <= k <= arr.length
• The maximum obtainable sum is at most 2147483647.