题目描述

给出整数数组 A，将该数组分隔为长度最多为 K 的几个（连续）子数组。分隔完成后，每个子数组的中的值都会变为该子数组中的最大值。

返回给定数组完成分隔后的最大和。

样例

输入：A = [1,15,7,9,2,5,10], K = 3
输出：84
解释：A 变为 [15,15,15,9,10,10,10]

注意

• 1 <= K <= A.length <= 500
• 0 <= A[i] <= 10^6

算法

(动态规划) $O(nK)$

1. $f(i)$ 表示划分了前 $i$ 个数字产生的最大和。这里的 $i$ 下标从 1 开始。
2. 初始时 $f(0) = 0$，其余为 -1。转移时，考虑第 $i$ 个数字与之前多少个数字组成一个 subarray。故枚举 $j$ 从 1 到 $K$，取 $f(i - j) + cur_max * j$ 的最大值。这里的 $cur_max$ 为区间的最大值，可以在枚举转移的时候更新。
3. 最终答案为 $f(n)$。

时间复杂度

• 状态数有 $O(n)$ 个，转移有 $O(K)$ 个，故需要 $O(nK)$ 的时间。

空间复杂度

• 只需要一个空间为 $O(n)$ 的数组，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& A, int K) {
        int n = A.size();
        vector<int> f(n + 1, -1);

        f[0] = 0;

        for (int i = 1; i <= n; i++) {
            int cur_max = -1;
            for (int j = 1; j <= K && i - j >= 0; j++) {
                cur_max = max(cur_max, A[i - j]);
                f[i] = max(f[i], f[i - j] + cur_max * j);
            }
        }

        return f[n];
    }
};