Problem

Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.

Examples

Example 1:

1
2
3
4
5

Input:
arr = [1,15,7,9,2,5,10], k = 3
Output:
 84
Explanation: arr becomes [15,15,15,9,10,10,10]

Example 2:

1
2
3
4

Input:
arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output:
 83

Example 3:

1
2
3
4

Input:
arr = [1], k = 1
Output:
 1

Solution

Method 1 – Dynamic Programming

Intuition

Use dynamic programming to find the maximum sum by considering all possible partitions of length up to k ending at each position.

Approach

  1. Let dp[i] be the maximum sum for the first i elements.
  2. For each position i, try all partition lengths j from 1 to k, and update dp[i] using the maximum value in the partition.
  3. The answer is dp[n], where n is the length of arr.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(n+1);
        for (int i = 1; i <= n; ++i) {
            int maxVal = 0;
            for (int j = 1; j <= k && i-j >= 0; ++j) {
                maxVal = max(maxVal, arr[i-j]);
                dp[i] = max(dp[i], dp[i-j] + maxVal * j);
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func maxSumAfterPartitioning(arr []int, k int) int {
    n := len(arr)
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        maxVal := 0
        for j := 1; j <= k && i-j >= 0; j++ {
            if arr[i-j] > maxVal { maxVal = arr[i-j] }
            if dp[i-j]+maxVal*j > dp[i] { dp[i] = dp[i-j]+maxVal*j }
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n+1];
        for (int i = 1; i <= n; ++i) {
            int maxVal = 0;
            for (int j = 1; j <= k && i-j >= 0; ++j) {
                maxVal = Math.max(maxVal, arr[i-j]);
                dp[i] = Math.max(dp[i], dp[i-j] + maxVal * j);
            }
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maxSumAfterPartitioning(arr: IntArray, k: Int): Int {
        val n = arr.size
        val dp = IntArray(n+1)
        for (i in 1..n) {
            var maxVal = 0
            for (j in 1..k) {
                if (i-j >= 0) {
                    maxVal = maxOf(maxVal, arr[i-j])
                    dp[i] = maxOf(dp[i], dp[i-j] + maxVal * j)
                }
            }
        }
        return dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxSumAfterPartitioning(self, arr: list[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n+1)
        for i in range(1, n+1):
            maxVal = 0
            for j in range(1, k+1):
                if i-j >= 0:
                    maxVal = max(maxVal, arr[i-j])
                    dp[i] = max(dp[i], dp[i-j] + maxVal * j)
        return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn max_sum_after_partitioning(arr: Vec<i32>, k: i32) -> i32 {
        let n = arr.len();
        let mut dp = vec![0; n+1];
        for i in 1..=n {
            let mut max_val = 0;
            for j in 1..=k as usize {
                if i >= j {
                    max_val = max_val.max(arr[i-j]);
                    dp[i] = dp[i].max(dp[i-j] + max_val * j as i32);
                }
            }
        }
        dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    maxSumAfterPartitioning(arr: number[], k: number): number {
        const n = arr.length;
        const dp = Array(n+1).fill(0);
        for (let i = 1; i <= n; ++i) {
            let maxVal = 0;
            for (let j = 1; j <= k && i-j >= 0; ++j) {
                maxVal = Math.max(maxVal, arr[i-j]);
                dp[i] = Math.max(dp[i], dp[i-j] + maxVal * j);
            }
        }
        return dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n*k)
    • For each position in the array (n), we check up to k possible partition lengths, resulting in O(n*k) total operations.
  • 🧺 Space complexity: O(n)
    • We use a DP array of size n+1 to store the maximum sum for each prefix of the array.