LeetCode 1043. Partition Array for Maximum Sum

Problem Statement

impl Solution {
    pub fn max_sum_after_partitioning(a: Vec<i32>, k: i32) -> i32 {
        let mut dp = vec![0; a.len() + 1];
        for i in 0..a.len() {
            let mut m = a[i];
            let mut j = 0;
            while j < k as usize && i >= j {
                m = std::cmp::max(m, a[i - j]);
                dp[i + 1] = std::cmp::max(dp[i + 1], dp[i + 1 - (j + 1)] + m * (j as i32 + 1));
                j += 1;
            }
        }

        return dp[a.len()];
    }
}