【Leetcode】1043. Partition Array for Maximum Sum

题目地址：

https://leetcode.com/problems/partition-array-for-maximum-sum/

给定一个长 n n n非负数组 A A A，和一个正整数 k k k，允许将 A A A划分为若干个长度小于等于 k k k的段，并且将每段里的数都改为这个段里的最大数。问改动后能得到的最大数组和是多少。

思路是动态规划。设 f [ i ] f[i] f[i]是 A [ 0 : i ] A[0:i] A[0:i]改动后能得到的最大和。那么可以按照最后一个数 A [ i ] A[i] A[i]是如何划分的来分类，它可能单独成一段，也可能和 A [ i − 1 ] A[i-1] A[i−1]成为长度为 2 2 2的段，最多可能和 A [ i − k + 1 ] A[i-k+1] A[i−k+1]成为长度为 k k k的段。所以 f [ i ] = max ⁡ i − k + 1 ≤ j ≤ i { f [ j − 1 ] + ( i − j + 1 ) max ⁡ j ≤ c ≤ i f [ c ] } f[i]=\max_{i-k+1\le j\le i}\{f[j-1]+(i-j+1)\max_{j\le c\le i} f[c]\} f[i]=i−k+1≤j≤imax​{f[j−1]+(i−j+1)j≤c≤imax​f[c]}初始条件 f [ 0 ] = A [ 0 ] f[0]=A[0] f[0]=A[0]。代码如下：

public class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            int max = arr[i];
            // 枚举最后一段的左端点
            for (int j = i; j >= 0 && i - j < k; j--) {
                max = Math.max(max, arr[j]);
                dp[i] = Math.max(dp[i], (j >= 1 ? dp[j - 1] : 0) + max * (i - j + 1));
            }
        }
        
        return dp[arr.length - 1];
    }
}
           

时间复杂度 O ( n k ) O(nk) O(nk)，空间 O ( n ) O(n) O(n)。