Approach #1: DFS + Memory. [Java]
class Solution {
public double largestSumOfAverages(int[] A, int K) {
int n = A.length;
double[][] memo = new double[K+1][n+1];
double[] sum = new double[n+1];
for (int i = 1; i <= n; ++i)
sum[i] += sum[i-1] + A[i-1];
return LSA(n, K, memo, sum);
}
public double LSA(int n, int k, double[][] memo, double[] sum) {
if (memo[k][n] > 0) return memo[k][n];
if (k == 1) return sum[n] / n;
for (int i = k - 1; i < n; ++i) {
memo[k][n] = Math.max(memo[k][n], LSA(i, k-1, memo, sum) + (sum[n] - sum[i]) / (n - i));
}
return memo[k][n];
}
}
Approach #2: DP. [C++]
class Solution {
public:
double largestSumOfAverages(vector<int>& A, int K) {
int n = A.size();
vector<vector<double>> dp(K+1, vector<double>(n+1, 0.0));
vector<double> sum(n+1, 0.0);
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i-1] + A[i-1];
dp[1][i] = static_cast<double>(sum[i]) / i;
}
for (int k = 2; k <= K; ++k)
for (int i = k; i <= n; ++i)
for (int j = k-1; j < i; ++j)
dp[k][i] = max(dp[k][i], dp[k-1][j] + (sum[i] - sum[j]) / (i - j));
return dp[K][n];
}
};