題目描述：

給定數(shù)組?nums?和一個整數(shù)?k?。我們將給定的數(shù)組?nums?分成 最多?k?個相鄰的非空子數(shù)組 。?分數(shù) 由每個子數(shù)組內(nèi)的平均值的總和構(gòu)成。

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設、高性價比鼎城網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式鼎城網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設找我們，業(yè)務覆蓋鼎城地區(qū)。費用合理售后完善，十多年實體公司更值得信賴。

注意我們必須使用 nums 數(shù)組中的每一個數(shù)進行分組，并且分數(shù)不一定需要是整數(shù)。

返回我們所能得到的大 分數(shù) 是多少。答案誤差在?10-6?內(nèi)被視為是正確的。

Level	AC rate
Medium	58.7%

題目解析：

一個元素要么自成一組要么并入前面的組，怎么并入形成的平均值大呢，如果該元素序號為i，那么就找前i個元素分為j-1組（不一定要完全包括i個元素）與剩余元素和當前元素之和的均值大值即可，前綴和的動態(tài)規(guī)劃，這里有一個值得注意的點是，for循環(huán)中的順序，外層應該為組數(shù)j，內(nèi)層為當前元素序號i，再內(nèi)層為分為j-1組的元素數(shù)選擇，因為每次計算需要知道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];
    }
};

執(zhí)行用時：16 ms, 在所有?C++?提交中擊敗了77.25%的用戶

內(nèi)存消耗：7.7 MB, 在所有?C++?提交中擊敗了58.98%的用戶

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：Leetcode813.最大平均值和的分組-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://weahome.cn/article/cossss.html