Code Implementation

from typing import List

class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]

        dp = [[0.0] * (k+1) for _ in range(n+1)]
        for i in range(1, n+1):
            dp[i][1] = prefix[i] / i

        for parts in range(2, k+1):
            for i in range(parts, n+1):
                for j in range(parts-1, i):
                    dp[i][parts] = max(dp[i][parts], dp[j][parts-1] + (prefix[i] - prefix[j]) / (i - j))
        return dp[n][k]
      

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> prefix(n+1, 0);
        for (int i = 0; i < n; ++i)
            prefix[i+1] = prefix[i] + nums[i];
        
        vector<vector<double>> dp(n+1, vector<double>(k+1, 0.0));
        for (int i = 1; i <= n; ++i)
            dp[i][1] = prefix[i] / i;
        
        for (int parts = 2; parts <= k; ++parts) {
            for (int i = parts; i <= n; ++i) {
                for (int j = parts-1; j < i; ++j) {
                    dp[i][parts] = max(dp[i][parts], dp[j][parts-1] + (prefix[i] - prefix[j]) / (i - j));
                }
            }
        }
        return dp[n][k];
    }
};
      

class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        double[] prefix = new double[n+1];
        for (int i = 0; i < n; ++i) {
            prefix[i+1] = prefix[i] + nums[i];
        }
        double[][] dp = new double[n+1][k+1];
        for (int i = 1; i <= n; ++i) {
            dp[i][1] = prefix[i] / i;
        }
        for (int parts = 2; parts <= k; ++parts) {
            for (int i = parts; i <= n; ++i) {
                for (int j = parts-1; j < i; ++j) {
                    dp[i][parts] = Math.max(dp[i][parts], dp[j][parts-1] + (prefix[i] - prefix[j]) / (i - j));
                }
            }
        }
        return dp[n][k];
    }
}
      

var largestSumOfAverages = function(nums, k) {
    const n = nums.length;
    const prefix = new Array(n+1).fill(0);
    for (let i = 0; i < n; ++i) {
        prefix[i+1] = prefix[i] + nums[i];
    }
    const dp = Array.from({length: n+1}, () => new Array(k+1).fill(0));
    for (let i = 1; i <= n; ++i) {
        dp[i][1] = prefix[i] / i;
    }
    for (let parts = 2; parts <= k; ++parts) {
        for (let i = parts; i <= n; ++i) {
            for (let j = parts-1; j < i; ++j) {
                dp[i][parts] = Math.max(dp[i][parts], dp[j][parts-1] + (prefix[i] - prefix[j]) / (i - j));
            }
        }
    }
    return dp[n][k];
};
      

Problem Description

• Each element in nums must be included in exactly one subarray.
• Each subarray must be contiguous (no skipping elements).
• You can use fewer than k partitions if it leads to a higher sum.
• Elements cannot be reused or split between subarrays.
• There is always at least one valid solution.

• nums: A list of positive integers.
• k: An integer representing the maximum number of partitions.

Thought Process

• We want to maximize the sum of averages, so it’s beneficial to separate large numbers into their own groups when possible.
• Since each subarray must be contiguous, we can use dynamic programming to build up solutions for smaller subarrays and use them to solve larger ones.
• By storing solutions to subproblems, we avoid recomputing the same results many times.

Solution Approach

1. Prefix Sums:
   • Calculate a prefix sum array so that you can quickly compute the sum of any subarray nums[i:j] as prefix[j] - prefix[i].
2. DP Table:
   • Create a 2D DP table dp[i][k] where dp[i][k] represents the largest sum of averages for the first i elements of nums using k partitions.
3. Base Case:
   • When there is only 1 partition (k=1), the best we can do is the average of the first i elements: dp[i][1] = prefix[i] / i.
4. DP Transition:
   • For more than 1 partition, try every possible previous split point j (where the last partition starts after j), and update dp[i][k] as:
   • dp[i][k] = max(dp[i][k], dp[j][k-1] + average(nums[j:i]))
   • Here, average(nums[j:i]) = (prefix[i] - prefix[j]) / (i - j)
5. Final Answer:
   • The answer is dp[n][k], where n is the length of nums.

Example Walkthrough

• Step 1: Compute Prefix Sums
  prefix = [0, 9, 10, 12, 15, 24]
• Step 2: Initialize Base Case (1 partition)
  
  • dp[1][1] = 9/1 = 9
  • dp[2][1] = 10/2 = 5
  • dp[3][1] = 12/3 = 4
  • dp[4][1] = 15/4 = 3.75
  • dp[5][1] = 24/5 = 4.8
• Step 3: Fill DP for 2 and 3 partitions
  • For dp[5][2], try splitting at each possible j:
  • Split at 1: dp[1][1] + average(1,5) = 9 + (24-9)/(5-1) = 9 + 3.75 = 12.75
  • Split at 2: dp[2][1] + average(2,5) = 5 + (24-10)/(5-2) = 5 + 4.67 = 9.67
  • Split at 3: ... and so on.
  • Take the maximum.
• Step 4: Continue for up to k=3 partitions
  • For dp[5][3], try splitting at each possible j where the previous partition ends.
  • Pick the maximum sum of averages over all valid splits.
• Final Answer:
  • dp[5][3] = 20

Time and Space Complexity

• Brute Force: Trying all possible partitions leads to exponential time complexity, specifically O(2ⁿ), which is not feasible for large arrays.
• Optimized DP Approach:
  • The DP table has size O(nk), where n is the length of nums and k is the maximum number of partitions.
  • For each dp[i][parts], we check up to i split points, so total time is O(n²k).
  • Space complexity is O(nk) for the DP table and O(n) for the prefix sum array.

Summary