分隔数组以得到最大和 - Partition Array for Maximum Sum

【动态规划】

Problem Link

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

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

Example:

示例：

输入：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

Analysis

具体每一段的分割长度未知，属于典型的动态规划问题。若考虑是否以当前位置的数字作为该段中的最大值，但难以保证这一段数组的区间。

具体思路如下：

定义 dp[i] 为子数组 A[0, i] 按照题意分割后的最大和（最优解）

定义最后一个分割区间长度 j，则显然 $j ∈ [1, K]$

定义最后一个分割区间最大值 domainMax，则有 $domainMax = max{A[i-j+1, i]}$

对于每种取值，均可更新最优解，因此转移公式为：

$$\begin{equation}dp[i]=\left{\begin{array}{lr}\text{dp[i],}&\quad\text{当前分割区间长度 j 不是最优解,}\text{dp[i-j] + j*domainMax,} &\quad\text{当前分割区间长度 j 是最优解.}\end{array}\right.\end{equation} $$

边界条件为 i < K，即必须满足 i - j >= 0 。

Solution 【动态规划】

执行用时 : 14 ms, 在Partition Array for Maximum Sum的Java提交中击败了88.89% 的用户

内存消耗 : 36 MB, 在Partition Array for Maximum Sum的Java提交中击败了100.00% 的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public int maxSumAfterPartitioning(int[] A, int K) {
        int len = A.length;
        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            /* 分别计算最后一段区间长度 j ∈[1, K]时的解，并更新位置i时的最优解 */
            int domainMax = A[i];
            for (int j = 1; j <= K && i - j + 1 >= 0; j++) {
                domainMax = Math.max(domainMax, A[i-j+1]);
                if (i - j >= 0) {
                    dp[i] = Math.max(dp[i], dp[i-j] + j*domainMax);
                } else {
                    dp[i] = Math.max(dp[i], j*domainMax);
                }
            }
        }
        return dp[len-1];
    }
}

复杂度分析

时间：$O(N*K)$

空间：$O(N)$

Notes

动态规划问题步骤

寻找最优解的表示
状态转移方程
边界条件判断