1
use std::cmp;
2

3
impl Solution {
4
  pub fn max_sum_after_partitioning(arr: Vec<i32>, k: i32) -> i32 {
5
    let mut k = k as usize;
6
    let n: usize = arr.len();
7
    let mut dp: Vec<i32> = vec![0; n + 1];
8
    dp[1] = arr[0];
9
    for i in 2..n + 1 as usize {
10
      let mut max_so_far: i32 = arr[i - 1];
11
      for j in 1..k + 1 as usize {
12
        if i < j {
13
          break;
14
        }
15
        max_so_far = cmp::max(max_so_far, arr[i - j]);
16
        dp[i] = cmp::max(dp[i], dp[i - j] + (j as i32) * max_so_far);
17
      }
18
    }
19
    dp[n]
20
  }
21
}