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 <stdio.h>
2#include <string.h>
3#include <math.h>
4
5#define MAX_N 100
6
7double largestSumOfAverages(int* nums, int numsSize, int k) {
8 double prefix_sum[MAX_N + 1];
9 double dp[MAX_N][MAX_N];
10 memset(dp, 0, sizeof(dp));
11
12 // Calculate prefix sums
13 prefix_sum[0] = 0;
14 for (int i = 0; i < numsSize; ++i) {
15 prefix_sum[i + 1] = prefix_sum[i] + nums[i];
16 }
17
18 // Base case for one partition
19 for (int i = 0; i < numsSize; ++i) {
20 dp[i][0] = (prefix_sum[numsSize] - prefix_sum[i]) / (numsSize - i);
21 }
22
23 // Fill dp for up to k partitions
24 for (int m = 1; m < k; ++m) {
25 for (int i = 0; i < numsSize; ++i) {
26 for (int j = i + 1; j < numsSize; ++j) {
27 dp[i][m] = fmax(dp[i][m], (prefix_sum[j] - prefix_sum[i]) / (j - i) + dp[j][m - 1]);
28 }
29 }
30 }
31
32 return dp[0][k - 1];
33}
34
35int main() {
36 int nums[] = {9, 1, 2, 3, 9};
37 int numsSize = 5;
38 int k = 3;
39 printf("%.5f\n", largestSumOfAverages(nums, numsSize, k));
40 return 0;
41}First, compute prefix sums for the array, then utilize dynamic programming to calculate the maximum sum of averages for each possible partition using the prefix sums. The dp array stores the maximum score achievable for each subarray starting at index i using up to m partitions.
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 C implementation defines a solve function that handles partitioning recursively, memoizing previously calculated scores to prevent redundant computation. This function checks scores for partitions from index i with m partitions left.