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
class Solution {
 public:
  double largestSumOfAverages(vector<int>& nums, int k) {
    const int n = nums.size();
    vector<vector<double>> mem(n + 1, vector<double>(k + 1));
    vector<double> prefix(n + 1);
    partial_sum(nums.begin(), nums.end(), prefix.begin() + 1);
    return largestSumOfAverages(nums, n, k, prefix, mem);
  }

 private:
  // Returns the maximum score to partition the first i numbers into k groups.
  double largestSumOfAverages(const vector<int>& nums, int i, int k,
                              const vector<double>& prefix,
                              vector<vector<double>>& mem) {
    if (k == 1)
      return prefix[i] / i;
    if (mem[i][k] > 0)
      return mem[i][k];

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

    return mem[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
class Solution {
  public double largestSumOfAverages(int[] nums, int k) {
    final int n = nums.length;
    double[][] mem = new double[n + 1][k + 1];
    double[] prefix = new double[n + 1];

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

    return largestSumOfAverages(nums, n, k, prefix, mem);
  }

  // Returns the maximum score to partition the first i numbers into k groups.
  private double largestSumOfAverages(int[] nums, int i, int k, double[] prefix, double[][] mem) {
    if (k == 1)
      return prefix[i] / i;
    if (mem[i][k] > 0)
      return mem[i][k];

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

    return mem[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] := the maximum score to partition the 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[] nums, int K) {
    final int n = nums.length;
    // dp[i][k] := the maximum score to partition the 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] = nums[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];
  }
}