# 1043. Partition Array for Maximum Sum

[Link](https://leetcode.com/problems/partition-array-for-maximum-sum/)

Given an integer array `arr`, you should 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: 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`

#### Solution

dp\[i] : the max result of arr\[0....i]

consider replacing the last k element of arr\[0...i] to the max value among them, to see if they can derive the max result:

dp\[i] = Math.max(dp\[i], dp\[i-k] + k\*curMax);

```java
class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n];
        int curMax;
        for(int i = 0; i < n; i++){
            curMax = 0;
            for(int j = 1; (j <= k)&&(i-j+1 >= 0); j++){
                curMax = Math.max(curMax, arr[i-j+1]);
                dp[i] = Math.max(dp[i], (i-j >= 0 ? dp[i-j] : 0) + curMax*j);
            }
        }
        return dp[n-1];
        
    }
}
```
