## 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 <= 500`
• `0 <= arr[i] <= 109`
• `1 <= 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];
};
``````
Copy The Code &

Input

cmd
arr = [1,15,7,9,2,5,10], k = 3

Output

cmd
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]
``````
Copy The Code &

Input

cmd
arr = [1,15,7,9,2,5,10], k = 3

Output

cmd
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];
}
}
}
``````
Copy The Code &

Input

cmd
arr = [1], k = 1

Output

cmd
1