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.

Return the maximum score you can get after partitioning the array.

Solution:

The given problem can be solved using dynamic programming. Let's define dp[i][j] as the maximum score we can get after partitioning the sub-array nums[0...i] into j partitions. Thus, our final answer would be dp[nums.length - 1][k] i.e. maximum score with k partitions over the entire array.

To compute the value of dp[i][j], we can iterate over all possible ending positions (say end) of the last partition and choose the maximum value of dp[end - 1][j - 1] + average(nums[end...i]). Here, average(nums[end...i]) is the average of the subarray nums[end...i]. It can be computed as (sum[i] - sum[end - 1]) / (i - end + 1) where sum[i] represents the sum of the subarray nums[0...i]. We can precompute all the prefix sums in the array sum to reduce time complexity.

Thus, our final dynamic programming formula would look something like this:

dp[i][j] = max(dp[end - 1][j - 1] + (sum[i] - sum[end - 1]) / (i - end + 1)) for end in [j - 1, i]

Here, we can start our loop for end from j - 1 as we need at least j sub-arrays to partition the sub-array nums[0...i] into j parts.

Finally, we can return dp[nums.length - 1][k] as the answer.

Time Complexity:

Our dynamic programming solution will have O(n^2 * k) time complexity where n is the length of the given array nums. The outer loop over i will run O(n) times, the inner loop over j will run O(k) times and the innermost loop over end will run O(n) times. Therefore, the overall time complexity would be O(n^2 * k).

Space Complexity:

We are using a two-dimensional dp array of size O(n * k) to compute the maximum score. Thus, our space complexity would be O(n * k).

Pseudo Code:

function largestSumOfAverages(nums, k): n = nums.length, dp = [[0] * (k + 1) for _ in range(n)] sum = [0] * n for i in range(n): sum[i] = (sum[i - 1] if (i > 0) else 0) + nums[i]

for i in range(n): for j in range(1, k + 1): if j == 1: dp[i][j] = (sum[i] / (i + 1)) else: for end in range(j - 1, i + 1): dp[i][j] = max(dp[i][j], dp[end - 1][j - 1] + (sum[i] - sum[end - 1]) / (i - end + 1))

return dp[n - 1][k]

Code in Python:

def largestSumOfAverages(nums, k): n, dp, sm = len(nums), [[0] * (k + 1) for _ in range(n)], [0] * n for i in range(n): sm[i] = (sm[i - 1] if (i > 0) else 0) + nums[i]

for i in range(n):
    for j in range(1, k + 1):
        if j == 1:
            dp[i][j] = (sm[i] / (i + 1))
        else:
            for end in range(j - 1, i + 1):
                dp[i][j] = max(dp[i][j], dp[end - 1][j - 1] + (sm[i] - sm[end - 1]) / (i - end + 1))

return dp[n - 1][k]

test the code with example inputs

print(largestSumOfAverages([9,1,2,3,9],3)) # Output: 20.00000

1