Sponsored
Sponsored
This approach utilizes dynamic programming combined with prefix sums to efficiently calculate the sum of subarray averages when partitioned optimally. The prefix sum array allows for quick computation of subarray sums, and dynamic programming is used to build the optimal solution up to k partitions.
Time Complexity: O(n^2 * k), where n is the length of the array, and k is the number of partitions.
Space Complexity: O(n * k) due to the dp table.
1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5using namespace std;
6
7double largestSumOfAverages(vector<int>& nums, int k) {
8 int n = nums.size();
9 vector<double> prefix_sum(n + 1, 0);
10 vector<vector<double>> dp(n, vector<double>(k, 0));
11
12 for (int i = 0; i < n; ++i) {
13 prefix_sum[i + 1] = prefix_sum[i] + nums[i];
14 }
15
16 for (int i = 0; i < n; ++i) {
17 dp[i][0] = (prefix_sum[n] - prefix_sum[i]) / (n - i);
18 }
19
20 for (int m = 1; m < k; ++m) {
21 for (int i = 0; i < n; ++i) {
22 for (int j = i + 1; j < n; ++j) {
23 dp[i][m] = max(dp[i][m], (prefix_sum[j] - prefix_sum[i]) / (j - i) + dp[j][m - 1]);
24 }
25 }
26 }
27
28 return dp[0][k - 1];
29}
30
31int main() {
32 vector<int> nums = {9, 1, 2, 3, 9};
33 int k = 3;
34 cout << fixed << setprecision(5) << largestSumOfAverages(nums, k) << endl;
35 return 0;
36}This code implementation follows the same logic as the C version but uses C++ vector for easier management of dynamic arrays. It iterates over possible partitions and leverages prefix sums to calculate subarray averages efficiently.
This approach uses recursion with memoization to solve for the maximum sum of averages by exploring all possible partition strategies and storing computed results for reuse. This avoids redundant computations and optimizes performance compared to plain recursion.
Time Complexity: O(n^2 * k) as each subproblem is solved once.
Space Complexity: O(n * k) for memoization table.
1
public class Solution {
private double[,] memo;
private double[] prefixSum;
private double Solve(int i, int k, int n) {
if (k == 1) return (prefixSum[n] - prefixSum[i]) / (n - i);
if (Math.Abs(memo[i, k] + 1) > 1e-9) return memo[i, k];
double maxScore = 0;
for (int j = i + 1; j <= n - (k - 1); ++j) {
maxScore = Math.Max(maxScore, (prefixSum[j] - prefixSum[i]) / (j - i) + Solve(j, k - 1, n));
}
return memo[i, k] = maxScore;
}
public double LargestSumOfAverages(int[] nums, int k) {
int n = nums.Length;
memo = new double[n, k + 1];
prefixSum = new double[n + 1];
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
for (int i = 0; i < n; ++i)
for (int j = 0; j <= k; ++j)
memo[i, j] = -1;
return Solve(0, k, n);
}
public static void Main() {
int[] nums = {9, 1, 2, 3, 9};
int k = 3;
Solution sol = new Solution();
Console.WriteLine(sol.LargestSumOfAverages(nums, k).ToString("F5"));
}
}This C# approach uses recursion and memoization for efficient calculation of maximum average sum combinations by maintaining a table of computed results to avoid repetitive calculations in recursive calls.