Skip to content

813. Largest Sum of Averages 👍

Approach 1: Top-down

  • Time: $O(Kn^2)$
  • Space: $O(Kn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  double largestSumOfAverages(vector<int>& nums, int K) {
    const int n = nums.size();
    // dp[i][k] := largest score to partition first i nums into k groups
    dp.resize(n + 1, vector<double>(K + 1));
    prefix.resize(n + 1);

    partial_sum(nums.begin(), nums.end(), prefix.begin() + 1);
    return largestSumOfAverages(nums, n, K);
  }

 private:
  vector<vector<double>> dp;
  vector<double> prefix;

  double largestSumOfAverages(const vector<int>& A, int i, int k) {
    if (k == 1)
      return prefix[i] / i;
    if (dp[i][k])
      return dp[i][k];

    // Try all possible partitions
    for (int j = k - 1; j < i; ++j)
      dp[i][k] = max(dp[i][k], largestSumOfAverages(A, j, k - 1) +
                                   (prefix[i] - prefix[j]) / (i - j));

    return dp[i][k];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public double largestSumOfAverages(int[] A, int K) {
    final int n = A.length;
    // dp[i][k] := largest score to partition first i nums into k groups
    dp = new double[n + 1][K + 1];
    prefix = new double[n + 1];

    for (int i = 0; i < n; ++i)
      prefix[i + 1] = A[i] + prefix[i];

    return largestSumOfAverages(A, n, K);
  }

  private double[][] dp;
  private double[] prefix;

  private double largestSumOfAverages(int[] A, int i, int k) {
    if (k == 1)
      return prefix[i] / i;
    if (dp[i][k] > 0.0)
      return dp[i][k];

    // Try all possible partitions
    for (int j = k - 1; j < i; ++j)
      dp[i][k] =
          Math.max(dp[i][k], largestSumOfAverages(A, j, k - 1) + (prefix[i] - prefix[j]) / (i - j));

    return dp[i][k];
  }
}

Approach 2: Bottom-up

  • Time: $O(Kn^2)$
  • Space: $O(Kn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  double largestSumOfAverages(vector<int>& nums, int K) {
    const int n = nums.size();
    // dp[i][k] := largest score to partition first i nums into k groups
    vector<vector<double>> dp(n + 1, vector<double>(K + 1));
    vector<double> prefix(n + 1);

    partial_sum(nums.begin(), nums.end(), prefix.begin() + 1);

    for (int i = 1; i <= n; ++i)
      dp[i][1] = prefix[i] / i;

    for (int k = 2; k <= K; ++k)
      for (int i = k; i <= n; ++i)
        for (int j = k - 1; j < i; ++j) {
          const double average = (prefix[i] - prefix[j]) / (i - j);
          dp[i][k] = max(dp[i][k], dp[j][k - 1] + average);
        }

    return dp[n][K];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public double largestSumOfAverages(int[] A, int K) {
    final int n = A.length;
    // dp[i][k] := largest score to partition first i nums into k groups
    double[][] dp = new double[n + 1][K + 1];
    double[] prefix = new double[n + 1];

    for (int i = 1; i <= n; ++i) {
      prefix[i] = A[i - 1] + prefix[i - 1];
      dp[i][1] = prefix[i] / i;
    }

    for (int k = 2; k <= K; ++k)
      for (int i = k; i <= n; ++i)
        for (int j = k - 1; j < i; ++j) {
          final double average = (prefix[i] - prefix[j]) / (i - j);
          dp[i][k] = Math.max(dp[i][k], dp[j][k - 1] + average);
        }

    return dp[n][K];
  }
}