Grokking 75: Top Coding Interview Questions

0% completed

​
Solution: Partition Array for Maximum Sum

Problem Statement

You are given an integer array arr, partition the array into subarrays of length at most k. After partitioning, change each element of a particular subarray to the maximum value of that subarray.

Return the largest possible sum of the array after partitioning.

Examples

Example 1:

  • Input: arr = [1, 3, 7, 9, 2], k = 2
  • Output: 33
  • Explanation:
    • Partition into [1], [3, 7], [9, 2].
    • Change subarrays to their max values: [1], [7, 7], [9, 9].
    • Sum is 1 + 7 + 7 + 9 + 9 = 33.

Example 2:

  • Input: arr =

.....

.....

.....

Like the course? Get enrolled and start learning!