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.
1function largestSumOfAverages(nums, k) {
2 const n = nums.length;
3 const prefixSum = new Array(n + 1).fill(0);
4 const dp = Array.from({ length: n }, () => new Array(k).fill(0));
5
6 for (let i = 0; i < n; ++i) {
7 prefixSum[i + 1] = prefixSum[i] + nums[i];
8 }
9
10 for (let i = 0; i < n; ++i) {
11 dp[i][0] = (prefixSum[n] - prefixSum[i]) / (n - i);
12 }
13
14 for (let m = 1; m < k; ++m) {
15 for (let i = 0; i < n; ++i) {
16 for (let j = i + 1; j < n; ++j) {
17 dp[i][m] = Math.max(dp[i][m], (prefixSum[j] - prefixSum[i]) / (j - i) + dp[j][m - 1]);
18 }
19 }
20 }
21
22 return dp[0][k - 1];
23}
24
25const nums = [9, 1, 2, 3, 9];
26const k = 3;
27console.log(largestSumOfAverages(nums, k).toFixed(5));This JavaScript solution replicates the logic of the other language implementations, using arrays to maintain prefix sums and a dynamic programming table to track the best partition combinations.
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
This Java implementation uses a similar strategy as other languages by defining a function to compute max partition scores recursively using memoization. It maintains prefix sums to compute averages efficiently and memoizes results to reduce recursive depth.