# 1043. Partition Array for Maximum Sum

Given an integer array `A`, you 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.

**Example 1:**

```
Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]
```

**Note:**

1. `1 <= K <= A.length <= 500`
2. `0 <= A[i] <= 10^6`

```cpp
// Dynamic Programming
int maxSumAfterPartitioning(vector<int>& A, int K) { // time: O(n * K); space: O(n)
    int n = A.size();
    vector<int> dp(n);
    for (int i = 0; i < n; ++i) {
        int curMax = 0;
        for (int j = 1; j <= K && i - j + 1 >= 0; ++j) {
            curMax = max(curMax, A[i - j + 1]);
            dp[i] = max(dp[i], (i >= j ? dp[i - j] : 0) + curMax * j);
        }
    }
    return dp.back();
}
```