Medium

题目描述

给定一个整数数组 nums 和一个整数 k。你可以将数组分割成最多 k 个非空的相邻子数组。分组的分数是每个子数组平均值的总和。

注意，分组必须使用 nums 中的每一个整数，并且分数不一定是整数。

返回所有可能分组中能够得到的最大分数。答案误差在 10^-6 内将被接受。

示例 1:

输入: nums = [9,1,2,3,9], k = 3
输出: 20.00000
解释: 
最佳选择是将 nums 分成 [9], [1, 2, 3], [9]。
答案是 9 + (1 + 2 + 3) / 3 + 9 = 20。
我们也可以将 nums 分成 [9, 1], [2], [3, 9]，例如，
那个分组将导致分数为 5 + 2 + 6 = 13，这更糟。

示例 2:

输入: nums = [1,2,3,4,5,6,7], k = 4
输出: 20.50000

约束条件:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

解题思路

这是一个典型的动态规划问题。我们需要将数组分割成最多k个子数组，使得各子数组平均值的和最大。

思路分析：

  1. 状态定义：设 dp[i][j] 表示将前 i 个元素分成 j 个组能得到的最大平均值和。

  2. 状态转移：对于 dp[i][j]，我们枚举最后一个组的起始位置 t，那么：

    • 前 t-1 个元素分成 j-1 个组：dp[t-1][j-1]
    • 第 t 到第 i 个元素组成最后一个组，其平均值为 (sum[i] - sum[t-1]) / (i - t + 1)
    • 状态转移方程：dp[i][j] = max(dp[t-1][j-1] + avg(t, i)) 对所有有效的 t

  3. 边界条件：

    • dp[i][1] = 前 i 个元素的平均值（只分成一组）
    • 当 j > i 时，无法分组，设为负无穷

  4. 优化技巧：

    • 使用前缀和快速计算子数组和
    • 注意数组下标的转换（题目从1开始，代码从0开始）

最终答案是 dp[n][k]，但由于可以分成"最多"k个组，还需要考虑分成少于k个组的情况，取所有 dp[n][j] (1≤j≤k) 的最大值。

代码实现

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> prefix(n + 1, 0);
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        // dp[i][j] 表示前i个元素分成j组的最大平均值和
        vector<vector<double>> dp(n + 1, vector<double>(k + 1, -1e9));
        
        // 初始化：分成1组的情况
        for (int i = 1; i <= n; i++) {
            dp[i][1] = prefix[i] / i;
        }
        
        // 动态规划
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= min(i, k); j++) {
                for (int t = j - 1; t < i; t++) {
                    double avg = (prefix[i] - prefix[t]) / (i - t);
                    dp[i][j] = max(dp[i][j], dp[t][j - 1] + avg);
                }
            }
        }
        
        // 返回最多k组的最大值
        double result = 0;
        for (int j = 1; j <= k; j++) {
            result = max(result, dp[n][j]);
        }
        return result;
    }
};

class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        n = len(nums)
        prefix = [0] * (n + 1)
        
        # 计算前缀和
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        # dp[i][j] 表示前i个元素分成j组的最大平均值和
        dp = [[-float('inf')] * (k + 1) for _ in range(n + 1)]
        
        # 初始化：分成1组的情况
        for i in range(1, n + 1):
            dp[i][1] = prefix[i] / i
        
        # 动态规划
        for i in range(2, n + 1):
            for j in range(2, min(i, k) + 1):
                for t in range(j - 1, i):
                    avg = (prefix[i] - prefix[t]) / (i - t)
                    dp[i][j] = max(dp[i][j], dp[t][j - 1] + avg)
        
        # 返回最多k组的最大值
        return max(dp[n][j] for j in range(1, k + 1))

public class Solution {
    public double LargestSumOfAverages(int[] nums, int k) {
        int n = nums.Length;
        double[] prefix = new double[n + 1];
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        // dp[i,j] 表示前i个元素分成j组的最大平均值和
        double[,] dp = new double[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = double.NegativeInfinity;
            }
        }
        
        // 初始化：分成1组的情况
        for (int i = 1; i <= n; i++) {
            dp[i, 1] = prefix[i] / i;
        }
        
        // 动态规划
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= Math.Min(i, k); j++) {
                for (int t = j - 1; t < i; t++) {
                    double avg = (prefix[i] - prefix[t]) / (i - t);
                    dp[i, j] = Math.Max(dp[i, j], dp[t, j - 1] + avg);
                }
            }
        }
        
        // 返回最多k组的最大值
        double result = 0;
        for (int j = 1; j <= k; j++) {
            result = Math.Max(result, dp[n, j]);
        }
        return result;
    }
}

var largestSumOfAverages = function(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    
    // 计算前缀和
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    // dp[i][j] 表示前i个元素分成j组的最大平均值和
    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(-Infinity));
    
    // 初始化：分成1组的情况
    for (let i = 1; i <= n; i++) {
        dp[i][1] = prefix[i] / i;
    }
    
    // 动态规划
    for (let i = 2; i <= n; i++) {
        for (let j = 2; j <= Math.min(i, k); j++) {
            for (let t = j - 1; t < i; t++) {
                const avg = (prefix[i] - prefix[t]) / (i - t);
                dp[i][j] = Math.max(dp[i][j], dp[t][j - 1] + avg);
            }
        }
    }
    
    // 返回最多k组的最大值
    let result = 0;
    for (let j = 1; j <= k; j++) {
        result = Math.max(result, dp[n][j]);
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²k)
空间复杂度O(nk)

其中 n 是数组长度。时间复杂度来自三层循环：外层遍历位置 i，中层遍历组数 j，内层遍历分割点 t。空间复杂度主要用于存储 dp 数组和前缀和数组。