Leetcode813.最大平均值和的分组-创新互联

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。

注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。

返回我们所能得到的大 分数 是多少。答案误差在 10-6 内被视为是正确的。

一个元素要么自成一组要么并入前面的组，怎么并入形成的平均值大呢，如果该元素序号为i，那么就找前i个元素分为j-1组（不一定要完全包括i个元素）与剩余元素和当前元素之和的均值大值即可，前缀和的动态规划，这里有一个值得注意的点是，for循环中的顺序，外层应该为组数j，内层为当前元素序号i，再内层为分为j-1组的元素数选择，因为每次计算需要知道j-1组的所有i值，代码如下：

class Solution {
public:
    double largestSumOfAverages(vector& nums, int k) {
        int len = nums.size();
        vectorpre(len+1);
        for(int i = 0 ; i< len ; i++){
            pre[i+1] = pre[i]+nums[i];
        }
        vector>dp(len+1,vector(k+1));
        for(int i = 0 ; i< len ; i++){
            dp[i+1][1] = pre[i+1]/(i+1);
        }
        for(int j = 2 ; j<= k ; j++){
            for(int i = j ; i<= len ; i++){
                for(int x = j-1 ; x< i ; x++){
                    dp[i][j] = max(dp[i][j],dp[x][j-1]+(pre[i]-pre[x])/(i-x));
                }
            }
        }
        return dp[len][k];
    }
};

执行用时：16 ms, 在所有 C++ 提交中击败了77.25%的用户

内存消耗：7.7 MB, 在所有 C++ 提交中击败了58.98%的用户

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧