## 1043. 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 = , k = 1
Output: 1
```

Constraints:

• `1 <= arr.length <= 500`
• `0 <= arr[i] <= 109`
• `1 <= k <= arr.length`

## Rust Solution

``````struct Solution;

impl Solution {
fn max_sum_after_partitioning(a: Vec<i32>, k: i32) -> i32 {
let n = a.len();
let mut dp = vec![0; n + 1];
let k = k as usize;
for r in 1..=n {
let l = r - 1;
let mut max = a[l];
for i in 0..k.min(r) {
max = max.max(a[l - i]);
dp[r] = dp[r].max(dp[l - i] + max * (i + 1) as i32);
}
}
dp[n]
}
}

#[test]
fn test() {
let a = vec![1, 15, 7, 9, 2, 5, 10];
let k = 3;
let res = 84;
assert_eq!(Solution::max_sum_after_partitioning(a, k), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.