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

0% completed

Vote For New Content
Partition Array for Maximum Sum (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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 = [4, 8, 1, 6, 5], k = 3
  • Output: 36
  • Explanation:
    • Partition into [4, 8, 1], [6, 5].
    • Change subarrays to their max values: [8, 8, 8], [6, 6].
    • Sum is 8 + 8 + 8 + 6 + 6 = 36.

Example 3:

  • Input: arr = [2, 5, 10, 1], k = 2
  • Output: 30
  • Explanation:
    • Partition into [2, 5], [10, 1].
    • Change subarrays to their max values: [5, 5], [10, 10].
    • Sum is 5 + 5 + 10 + 10 = 30.

Constraints:

  • 1 <= arr.length <= 500
  • 0 <= arr[i] <= 10<sup>9</sup>
  • 1 <= k <= arr.length

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible