[Leetcode 1043] Partition Array for Maximum Sum

原题说明

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K.  After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

Note:

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

解题思路

动态规划，用p[i]来表示A中前i个元素能够得到的最大值。
对于下一位dp[i + 1](即新加入元素A[i])来说，我们将以A[i]结尾的切分(partition)的长度从len = 1开始向前遍历，直到达到长度上限K：len = K
或者达到最左边：i - len + 1 = 0

对于每一个以A[i]结尾的切分长度len，我们首先计算该切分中的最大值（即从i到i - len + 1之间A的最大值），用max_value表示：
max_value = max(max_value, A[i - len + 1]);
然后将dp[i + 1]的值更新为：
max(dp[i + 1], max_value * len + dp[i - len + 1])

返回dp数组最后一个值：dp[A.size()]

示例代码 (cpp)

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& A, int K) {
        // 最左边dp[0]始终为0，可以不用判断最左边的边界条件
        vector<int> dp(A.size() + 1, 0);
        // i为A的index
        for (int i = 0; i < A.size(); ++i) {
            int max_value = 0;
            for (int len = 1; len <= K && i - len + 1 >= 0; ++len) {
                max_value = max(max_value, A[i - len + 1]);
                // dp的index相比A的index右移一格
                dp[i + 1] = max(dp[i + 1], max_value * len + dp[i - len + 1]);
            }
        }
        return dp[A.size()];
    }
};

示例代码 (java)

class Solution {
    public int maxSumAfterPartitioning(int[] A, int K) {
        int N = A.length, dp[] = new int[N];
        for (int i = 0; i < N; ++i) {
            int curMax = 0;
            for (int k = 1; k <= K && i - k + 1 >= 0; ++k) {
                curMax = Math.max(curMax, A[i - k + 1]);
                dp[i] = Math.max(dp[i], (i >= k ? dp[i - k] : 0) + curMax * k);
            }
        }
        return dp[N - 1];
    }
}

示例代码 (python)

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        N = len(A)
        dp = [0] * (N + 1)
        for i in range(N):
            curMax = 0
            for k in range(1, min(K, i + 1) + 1):
                curMax = max(curMax, A[i - k + 1])
                dp[i] = max(dp[i], dp[i - k] + curMax * k)
        return dp[N - 1]

复杂度分析

时间复杂度: O(N * K), N为数组A的长度
空间复杂度: O(N)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！