Partition Array for Maximum Sum

Problem Statement

Given an integer array arr and an integer k, partition the array into contiguous subarrays of length at most k. After partitioning, each element in a subarray is replaced by the maximum value of that subarray. Return the largest possible sum of the modified array.

For example, with arr = [1, 15, 7, 9, 2, 5] and k = 3:

• Partition into [1, 15, 7] and [9, 2, 5]
• First subarray: max = 15, so all elements become 15 → [15, 15, 15]
• Second subarray: max = 9, so all elements become 9 → [9, 9, 9]
• Modified array: [15, 15, 15, 9, 9, 9]
• Sum = 15 + 15 + 15 + 9 + 9 + 9 = 72

Other partitions give smaller sums. For instance, [1] and [15, 7, 9] and [2, 5] would give 1 + 15×3 + 5×2 = 56.