这个题的知识点很多呀，分割组块。最终用二维dp进行递归。
图片.png
- code:
double LSA(vector<int>& a, int n, int k, vector<vector<double>>& dp, vector<double> sum_) {
if (dp[k][n] > 0)
return dp[k][n];
if (k == 1)
return sum_[n] / (n + 1);
for (int i = 0; i < n; i++) {
dp[k][n] = max(dp[k][n], LSA(a, i, k - 1,dp,sum_) + (sum_[n] - sum_[i]) / (n - i));
}
return dp[k][n];
}
double largestSumOfAverages(vector<int>& A, int K) {
vector<double> sum_(A.begin(),A.end());
for (int i = 1; i < A.size(); i++)
sum_[i] = sum_[i - 1] + A[i];
vector<vector<double>> dp(K+1, vector<double>(A.size(), 0.0));
return LSA(A, A.size()-1, K,dp,sum_);
}
