classSolution{public:doublelargestSumOfAverages(vector<int>&nums,intK){constintn=nums.size();// dp[i][k] := largest score to partition first i nums into k groupsdp.resize(n+1,vector<double>(K+1));prefix.resize(n+1);partial_sum(begin(nums),end(nums),begin(prefix)+1);returnlargestSumOfAverages(nums,n,K);}private:vector<vector<double>>dp;vector<double>prefix;doublelargestSumOfAverages(constvector<int>&A,inti,intk){if(k==1)returnprefix[i]/i;if(dp[i][k])returndp[i][k];// Try all possible partitionsfor(intj=k-1;j<i;++j)dp[i][k]=max(dp[i][k],largestSumOfAverages(A,j,k-1)+(prefix[i]-prefix[j])/(i-j));returndp[i][k];}};
classSolution{publicdoublelargestSumOfAverages(int[]A,intK){finalintn=A.length;// dp[i][k] := largest score to partition first i nums into k groupsdp=newdouble[n+1][K+1];prefix=newdouble[n+1];for(inti=0;i<n;++i)prefix[i+1]=A[i]+prefix[i];returnlargestSumOfAverages(A,n,K);}privatedouble[][]dp;privatedouble[]prefix;privatedoublelargestSumOfAverages(int[]A,inti,intk){if(k==1)returnprefix[i]/i;if(dp[i][k]>0.0)returndp[i][k];// Try all possible partitionsfor(intj=k-1;j<i;++j)dp[i][k]=Math.max(dp[i][k],largestSumOfAverages(A,j,k-1)+(prefix[i]-prefix[j])/(i-j));returndp[i][k];}}
classSolution{public:doublelargestSumOfAverages(vector<int>&nums,intK){constintn=nums.size();// dp[i][k] := largest score to partition first i nums into k groupsvector<vector<double>>dp(n+1,vector<double>(K+1));vector<double>prefix(n+1);partial_sum(begin(nums),end(nums),begin(prefix)+1);for(inti=1;i<=n;++i)dp[i][1]=prefix[i]/i;for(intk=2;k<=K;++k)for(inti=k;i<=n;++i)for(intj=k-1;j<i;++j){constdoubleaverage=(prefix[i]-prefix[j])/(i-j);dp[i][k]=max(dp[i][k],dp[j][k-1]+average);}returndp[n][K];}};