# Largest Sum of Averages
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-sum-of-averages)
Canonical: https://scaleengineer.com/dsa/problems/largest-sum-of-averages
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force Recursion
This approach involves exploring all possible ways to partition the array into `k` groups using recursion. For each state, defined by the current starting index and the number of partitions remaining, we try every possible split point for the next partition and recursively solve for the rest of the array. This method exhaustively checks every valid partition scheme.
**Time:** Exponential, roughly O(n^k). The number of ways to partition n items into k groups is C(n-1, k-1), which grows very quickly. · **Space:** O(n) or O(k) for the recursion call stack, whichever is larger. Given k <= n, it's O(n).
**Pros:** Simple to conceive and directly models the problem statement.; Serves as a good foundation for more optimized dynamic programming solutions.
**Cons:** Extremely inefficient due to a large number of overlapping subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
### Explanation
The core idea is to define a function that solves the problem for a suffix of the array. Let's say `solve(i, p)` calculates the maximum score for partitioning `nums[i:]` into `p` groups.

To calculate `solve(i, p)`, we can form the first group by taking `nums[i...j]` for any valid `j`. The score for this choice would be the average of `nums[i...j]` plus the result of recursively solving for the rest of the array, `solve(j+1, p-1)`. We want to maximize this value over all possible `j`.

To avoid recomputing sums for averages repeatedly, we can use a prefix sum array. `prefixSum[x]` will store the sum of elements from `nums[0]` to `nums[x-1]`. The sum of `nums[i...j]` can then be found in O(1) time as `prefixSum[j+1] - prefixSum[i]`.

This method is a direct translation of the problem's combinatorial nature but suffers from massive re-computation of the same subproblems, leading to exponential time complexity.

```java
class Solution {
    private int[] nums;
    private int n;
    private double[] prefixSum;

    public double largestSumOfAverages(int[] nums, int k) {
        this.nums = nums;
        this.n = nums.length;
        this.prefixSum = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        return solve(0, k);
    }

    private double solve(int startIndex, int partitionsLeft) {
        if (startIndex == n) {
            return 0;
        }
        if (partitionsLeft == 1) {
            return (prefixSum[n] - prefixSum[startIndex]) / (n - startIndex);
        }

        double maxScore = 0;
        for (int i = startIndex; i <= n - partitionsLeft; i++) {
            double currentAverage = (prefixSum[i + 1] - prefixSum[startIndex]) / (i - startIndex + 1);
            maxScore = Math.max(maxScore, currentAverage + solve(i + 1, partitionsLeft - 1));
        }
        return maxScore;
    }
}
```
### Algorithm
- Define a recursive function, let's call it `solve(startIndex, partitionsLeft)`, which computes the maximum score for partitioning the subarray `nums[startIndex:]` into `partitionsLeft` groups.
- **Base Case 1:** If `partitionsLeft` is 1, we must group the entire remaining subarray `nums[startIndex:]`. The score is its average. Return this value.
- **Base Case 2:** If `startIndex` reaches the end of the array, we can't form any more non-empty partitions. Handle this boundary condition (e.g., return 0 if `partitionsLeft` is also 0, otherwise a very small number to signify an invalid path).
- **Recursive Step:** Iterate through all possible end points `i` for the first partition, which would be `nums[startIndex...i]`. The number of elements in the remaining subarray must be at least `partitionsLeft - 1`.
- For each choice of `i`, calculate the score as `average(nums[startIndex...i]) + solve(i + 1, partitionsLeft - 1)`.
- The function returns the maximum score found among all possible choices for `i`.
- The initial call to start the process is `solve(0, k)`.
- To calculate averages efficiently, pre-compute a prefix sum array.

## Top-Down Dynamic Programming with Memoization
This approach optimizes the brute-force recursion by using memoization, a top-down dynamic programming technique. We store the results of solved subproblems (identified by `startIndex` and `partitionsLeft`) in a cache or memoization table. When the same subproblem is encountered again, we retrieve the result from the cache instead of re-computing it, drastically reducing the number of calculations.
**Time:** O(n² * k). There are `n * k` possible states for `(startIndex, partitionsLeft)`. Each state takes O(n) time to compute due to the loop for finding the split point. · **Space:** O(n * k) for the memoization table, plus O(n) for prefix sums and the recursion stack.
**Pros:** Significantly more efficient than brute force and is fast enough to pass the given constraints.; Maintains a clear, logical structure that is easy to follow from the initial recursive idea.
**Cons:** The space complexity of O(n*k) might be a concern for larger constraints, though it's acceptable here.; Recursive solutions can sometimes lead to stack overflow errors for very deep recursion depths (not an issue for the given constraints).
### Explanation
The recursive structure reveals a large number of overlapping subproblems. For example, `solve(5, 2)` might be called after partitioning `[0...2]` and `[3...4]`, and also after partitioning `[0...3]` and `[4...4]`. Memoization avoids this redundant work.

We define a 2D array, `memo[n][k+1]`, where `memo[i][p]` stores the result of `solve(i, p)`. The function logic remains the same, but with an added check at the beginning to see if the result is already in our memo table. This turns the exponential complexity of the brute-force solution into a polynomial one.

```java
class Solution {
    private int n;
    private double[] prefixSum;
    private double[][] memo;

    public double largestSumOfAverages(int[] nums, int k) {
        this.n = nums.length;
        this.prefixSum = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        this.memo = new double[n][k + 1];
        return solve(0, k);
    }

    private double solve(int startIndex, int partitionsLeft) {
        if (startIndex == n) {
            return 0;
        }
        if (partitionsLeft == 1) {
            return (prefixSum[n] - prefixSum[startIndex]) / (n - startIndex);
        }
        if (memo[startIndex][partitionsLeft] != 0) {
            return memo[startIndex][partitionsLeft];
        }

        double maxScore = 0;
        for (int i = startIndex; i <= n - partitionsLeft; i++) {
            double currentAverage = (prefixSum[i + 1] - prefixSum[startIndex]) / (i - startIndex + 1);
            maxScore = Math.max(maxScore, currentAverage + solve(i + 1, partitionsLeft - 1));
        }
        
        memo[startIndex][partitionsLeft] = maxScore;
        return maxScore;
    }
}
```
### Algorithm
- Create a 2D memoization table, `memo[n][k+1]`, to store the results of subproblems. Initialize it with a value indicating that the state has not been computed (e.g., 0 or -1).
- Use the same recursive function `solve(startIndex, partitionsLeft)` as in the brute-force approach.
- At the beginning of the function, check if `memo[startIndex][partitionsLeft]` has already been computed. If so, return the stored value immediately.
- If not, compute the result as before by iterating through all possible split points.
- Before returning the computed maximum score, store it in `memo[startIndex][partitionsLeft]`.
- Pre-computing prefix sums is still beneficial for O(1) average calculation.

## Bottom-Up Dynamic Programming (Space Optimized)
This is a bottom-up, iterative dynamic programming solution. Instead of starting from the whole problem and breaking it down, we build the solution from the smallest subproblems up. We calculate the optimal scores for 1 partition, then use those results to find the optimal scores for 2 partitions, and so on, up to `k` partitions. This approach can be space-optimized.
**Time:** O(n² * k). The three nested loops for `p`, `i`, and `j` dominate the runtime. · **Space:** O(n). We use a 1D array `dp` of size `n+1` and a prefix sum array of size `n+1`.
**Pros:** Most efficient approach in terms of space complexity.; Avoids recursion overhead, which can lead to slightly better performance in practice.; Guaranteed not to have stack overflow issues.
**Cons:** The logic, especially the nested loops and state transitions, can be less intuitive to grasp compared to the recursive top-down approach.
### Explanation
We can define our DP state `dp[i][p]` as the largest sum of averages for partitioning the prefix `nums[0...i-1]` into `p` groups. The recurrence relation is:
`dp[i][p] = max_{p-1 <= j < i} (dp[j][p-1] + average(nums[j...i-1]))`

This would require an `O(n*k)` DP table. However, we can observe that to compute the values for `p` partitions, we only need the results from `p-1` partitions. This allows for a space optimization. We can use a single 1D array, `dp[n+1]`, where `dp[i]` stores the max score for partitioning `nums[0...i-1]` into the current number of partitions being considered.

We first fill the `dp` array for `p=1`. Then, for each subsequent `p` from 2 to `k`, we update the `dp` array. To use a single array, we must iterate the prefix length `i` from `n` down to `p`. This ensures that when we calculate `dp[i]` (for `p` partitions), the values `dp[j]` (where `j < i`) we access are still from the previous iteration (`p-1` partitions).

```java
class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        double[] prefixSum = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        double[] dp = new double[n + 1];

        // Base case: p = 1 partition
        for (int i = 1; i <= n; i++) {
            dp[i] = prefixSum[i] / i;
        }

        // Iterate for p = 2 to k partitions
        for (int p = 2; p <= k; p++) {
            // Iterate backwards for prefix length i
            for (int i = n; i >= p; i--) {
                // Iterate through split points j
                for (int j = i - 1; j >= p - 1; j--) {
                    double lastGroupAverage = (prefixSum[i] - prefixSum[j]) / (i - j);
                    dp[i] = Math.max(dp[i], dp[j] + lastGroupAverage);
                }
            }
        }

        return dp[n];
    }
}
```
### Algorithm
- Create a prefix sum array `prefix` of size `n+1`.
- Create a 1D DP array `dp` of size `n+1`. `dp[i]` will store the maximum score for partitioning the prefix `nums[0...i-1]`.
- **Handle the base case (1 partition):** Initialize `dp[i]` to be the average of the prefix `nums[0...i-1]`. This is `prefix[i] / i`.
- **Iterate for more partitions:** Loop for the number of partitions `p` from 2 to `k`.
  - Inside this loop, iterate through the prefix lengths `i` from `n` down to `p`.
  - For each `i`, iterate through possible split points `j` from `i-1` down to `p-1`.
  - The last group is `nums[j...i-1]`. The previous `p-1` groups partition `nums[0...j-1]`. The score for this is `dp[j]`. Note that since we iterate `i` downwards, `dp[j]` still holds the value from the `p-1` partitions step.
  - Update `dp[i]` with the maximum value found: `dp[i] = max(dp[i], dp[j] + average(nums[j...i-1]))`.
- After all loops complete, `dp[n]` will hold the maximum score for partitioning the entire array `nums` into `k` groups.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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);
  }
};

```

### Python

```python
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)

```