Grokking 75: Top Coding Interview Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Partition Array for Maximum Sum
On this page

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!

On this page