【2022-11-28每日一题】813. 最大平均值和的分组[Medium]

2022-11-28每日一题：813. 最大平均值和的分组

难度：Medium

标签：数组 、 动态规划 、 前缀和

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 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] <= 104
• 1 <= k <= nums.length

方法一：动态规划

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func largestSumOfAverages(nums []int, k int) float64 {
    n := len(nums)
    prefix := make([]float64, n+1)
    for i, x := range nums {
        prefix[i+1] = prefix[i] + float64(x)
    }
    dp := make([][]float64, n+1)
    for i := range dp {
        dp[i] = make([]float64, k+1)
    }
    for i := 1; i <= n; i++ {
        dp[i][1] = prefix[i] / float64(i)
    }
    for j := 2; j <= k; j++ {
        for i := j; i <= n; i++ {
            for x := j - 1; x < i; x++ {
                dp[i][j] = math.Max(dp[i][j], dp[x][j-1]+(prefix[i]-prefix[x])/float64(i-x))
            }
        }
    }
    return dp[n][k]
}

优化版本

func largestSumOfAverages(nums []int, k int) float64 {
    n := len(nums)
    prefix := make([]float64, n+1)
    for i, x := range nums {
        prefix[i+1] = prefix[i] + float64(x)
    }
    dp := make([]float64, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = prefix[i] / float64(i)
    }
    for j := 2; j <= k; j++ {
        for i := n; i >= j; i-- {
            for x := j - 1; x < i; x++ {
                dp[i] = math.Max(dp[i], dp[x]+(prefix[i]-prefix[x])/float64(i-x))
            }
        }
    }
    return dp[n]
}

复杂度分析

• 时间复杂度：O(k×n^2)，其中 k 是分组的最大子数组数目，n 是数组 nums 的长度。计算前缀和需要 O(n) 的时间，动态规划需要计算 O(k×n) 个状态，每个状态的计算时间是 O(n)。

• 空间复杂度：O(k×n) 或 O(n)，其中 k 是分组的最大子数组数目，nnn 是数组 nums 的长度。二维数组实现的空间复杂度是 O(k×n)，一维数组实现的空间复杂度是 O(n)。

方法二：前缀和 + 记忆化搜索

• 推荐题解

func largestSumOfAverages(nums []int, k int) float64 {
    n := len(nums)
    s := make([]int, n+1)
    f := [110][110]float64{}
    for i, v := range nums {
        s[i+1] = s[i] + v
    }
    var dfs func(i, k int) float64
    dfs = func(i, k int) float64 {
        if i == n {
            return 0
        }
        if k == 1 {
            return float64(s[n]-s[i]) / float64(n-i)
        }
        if f[i][k] > 0 {
            return f[i][k]
        }
        var ans float64
        for j := i; j < n; j++ {
            t := float64(s[j+1]-s[i])/float64(j-i+1) + dfs(j+1, k-1)
            ans = math.Max(ans, t)
        }
        f[i][k] = ans
        return ans
    }
    return dfs(0, k)
}

复杂度分析

• 时间复杂度 O(n^2×k)，
• 空间复杂度 O(n×k)。其中 n 表示数组 nums 的长度

LeetCode题库地址

• https://leetcode.cn/problems/largest-sum-of-averages