You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

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

. 2 min read

【动态规划】

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

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

Example:

示例:

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

提示:

  1. 1 <= K <= A.length <= 500
  2. 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% 的用户

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

动态规划问题步骤

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