Algorithm
Problem Name: 1043. Partition Array for Maximum Sum
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.
Example 1:
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:
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4 Output: 83
Example 3:
Input: arr = [1], k = 1 Output: 1
Constraints:
1 <= arr.length <= 5000 <= arr[i] <= 1091 <= k <= arr.length
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const maxSumAfterPartitioning = function(A, K) {
const N = A.length
const dp = new Array(N).fill(0);
for (let i = 0; i < N; ++i) {
let curMax = 0;
for (let j = 1; j < = K && i - j + 1 >= 0; j++) {
curMax = Math.max(curMax, A[i - j + 1]);
dp[i] = Math.max(dp[i], (i >= j ? dp[i - j] : 0) + curMax * j);
}
}
return dp[N - 1];
};
Input
arr = [1,15,7,9,2,5,10], k = 3
Output
84
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
N = len(A)
dp = [0] * (N + K)
for i in range(N):
curMax = 0
for k in range(1, min(K, i + 1) + 1):
curMax = max(curMax, A[i - k + 1])
dp[i] = max(dp[i], dp[i - k] + curMax * k)
return dp[N - 1]
Input
arr = [1,15,7,9,2,5,10], k = 3
Output
84
#3 Code Example with C# Programming
Code -
C# Programming
sing System;
namespace LeetCode
{
public class _1043_PartitionArrayForMaximumSum
{
public int MaxSumAfterPartitioning(int[] A, int K)
{
int N = A.Length;
var dp = new int[N];
for (int i = 0; i < N; i++)
{
var currMax = A[i];
for (int k = 1; k < = K && i - k + 1 >= 0; k++)
{
currMax = Math.Max(currMax, A[i - k + 1]);
dp[i] = Math.Max(dp[i], (i >= k ? dp[i - k] : 0) + currMax * k);
}
}
return dp[N - 1];
}
}
}
Input
arr = [1], k = 1
Output
1