Medium

题目描述

给你一个整数数组 arr，请你将数组分割为长度最多为 k 的一些（连续）子数组。分割完成后，每个子数组的值都会变为该子数组中的最大值。

请你返回将数组分割变换后能够得到的元素最大和。生成的测试用例满足答案是一个 32 位整数。

示例 1：

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]

示例 2：

输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83

示例 3：

输入：arr = [1], k = 1
输出：1

提示：

  • 1 <= arr.length <= 500
  • 0 <= arr[i] <= 10^9
  • 1 <= k <= arr.length

解题思路

这是一道经典的动态规划问题。我们需要将数组分割成长度不超过k的连续子数组，使得分割后的总和最大。

核心思路： 定义 dp[i] 表示前 i 个元素能够得到的最大和。对于位置 i，我们可以考虑最后一个子数组的长度为 j（1 <= j <= min(i, k)），这个子数组包含元素 arr[i-j] 到 arr[i-1]。

状态转移方程：

dp[i] = max(dp[i-j] + max_val * j)

其中 j 从 1 到 min(i, k)，max_val 是子数组 arr[i-j:i] 中的最大值。

算法步骤：

  1. 初始化 dp 数组，dp[0] = 0 表示空数组的最大和为0
  2. 对于每个位置 i，枚举最后一个子数组的长度 j
  3. 计算子数组 arr[i-j:i] 的最大值
  4. 更新 dp[i] = max(dp[i], dp[i-j] + max_val * j)
  5. 返回 dp[n]

时间复杂度为 O(nk)，空间复杂度为 O(n)，其中 n 是数组长度。

代码实现

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(n + 1, 0);
        
        for (int i = 1; i <= n; i++) {
            int maxVal = 0;
            for (int j = 1; j <= min(i, k); j++) {
                maxVal = max(maxVal, arr[i - j]);
                dp[i] = max(dp[i], dp[i - j] + maxVal * j);
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n + 1)
        
        for i in range(1, n + 1):
            max_val = 0
            for j in range(1, min(i, k) + 1):
                max_val = max(max_val, arr[i - j])
                dp[i] = max(dp[i], dp[i - j] + max_val * j)
        
        return dp[n]

public class Solution {
    public int MaxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.Length;
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            int maxVal = 0;
            for (int j = 1; j <= Math.Min(i, k); j++) {
                maxVal = Math.Max(maxVal, arr[i - j]);
                dp[i] = Math.Max(dp[i], dp[i - j] + maxVal * j);
            }
        }
        
        return dp[n];
    }
}

var maxSumAfterPartitioning = function(arr, k) {
    const n = arr.length;
    const dp = new Array(n + 1).fill(0);
    
    for (let i = 1; i <= n; i++) {
        let maxVal = 0;
        for (let j = 1; j <= Math.min(i, k); j++) {
            maxVal = Math.max(maxVal, arr[i - j]);
            dp[i] = Math.max(dp[i], dp[i - j] + maxVal * j);
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(nk)需要遍历n个位置，每个位置最多考虑k种分割方式
空间复杂度O(n)使用dp数组存储状态

相关题目