Question

813. Largest Sum of Averages

中文文档

Description

You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in nums, and that the score is not necessarily an integer.

Return _the maximum score you can achieve of all the possible partitions_. Answers within 10-6 of the actual answer will be accepted.

 

Example 1:

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

Example 2:

Input: nums = [1,2,3,4,5,6,7], k = 4
Output: 20.50000

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 104
• 1 <= k <= nums.length

Solutions

Solution 1

class Solution:
  def largestSumOfAverages(self, nums: List[int], k: int) -> float:
    @cache
    def dfs(i, k):
      if i == n:
        return 0
      if k == 1:
        return (s[-1] - s[i]) / (n - i)
      ans = 0
      for j in range(i, n):
        t = (s[j + 1] - s[i]) / (j - i + 1) + dfs(j + 1, k - 1)
        ans = max(ans, t)
      return ans

    n = len(nums)
    s = list(accumulate(nums, initial=0))
    return dfs(0, k)

class Solution {
  private Double[][] f;
  private int[] s;
  private int n;

  public double largestSumOfAverages(int[] nums, int k) {
    n = nums.length;
    s = new int[n + 1];
    f = new Double[n + 1][k + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    return dfs(0, k);
  }

  private double dfs(int i, int k) {
    if (i == n) {
      return 0;
    }
    if (k == 1) {
      return (s[n] - s[i]) * 1.0 / (n - i);
    }
    if (f[i][k] != null) {
      return f[i][k];
    }
    double ans = 0;
    for (int j = i; j < n; ++j) {
      double t = (s[j + 1] - s[i]) * 1.0 / (j - i + 1) + dfs(j + 1, k - 1);
      ans = Math.max(ans, t);
    }
    return f[i][k] = ans;
  }
}

class Solution {
public:
  double largestSumOfAverages(vector<int>& nums, int k) {
    int n = nums.size();
    int s[n + 1];
    double f[n][k + 1];
    s[0] = 0;
    memset(f, 0, sizeof f);
    for (int i = 0; i < n; ++i) s[i + 1] = s[i] + nums[i];
    function<double(int, int)> dfs = [&](int i, int k) -> double {
      if (i == n) return 0;
      if (k == 1) return (s[n] - s[i]) * 1.0 / (n - i);
      if (f[i][k]) return f[i][k];
      double ans = 0;
      for (int j = i; j < n; ++j) {
        double t = (s[j + 1] - s[i]) * 1.0 / (j - i + 1) + dfs(j + 1, k - 1);
        ans = max(ans, t);
      }
      return f[i][k] = ans;
    };
    return dfs(0, k);
  }
};

func largestSumOfAverages(nums []int, k int) float64 {
  n := len(nums)
  s := make([]int, n+1)
  f := [110][110]float64{}
  for i, v := range nums {
    s[i+1] = s[i] + v
  }
  var dfs func(i, k int) float64
  dfs = func(i, k int) float64 {
    if i == n {
      return 0
    }
    if k == 1 {
      return float64(s[n]-s[i]) / float64(n-i)
    }
    if f[i][k] > 0 {
      return f[i][k]
    }
    var ans float64
    for j := i; j < n; j++ {
      t := float64(s[j+1]-s[i])/float64(j-i+1) + dfs(j+1, k-1)
      ans = math.Max(ans, t)
    }
    f[i][k] = ans
    return ans
  }
  return dfs(0, k)
}