Largest Sum of Averages

Approach 1- Recursive

The brute force approach to the problem would be to try every possible partition and find the one with the maximum average sum. For doing so, we’ll write a recursive function largestSumOfAveragesRec() that will make ‘K’ partitions and maximize the average sum after every cycle. Let's see what this function will do.

largestSumOfAveragesRec()

Arguments

1. ‘N’ - Size of the array.
2. ‘ARR’ - Array.
3. ‘START’ - Start of the current partition.
4. ‘K’ - Number of partitions to be made.
5. ‘SUM’ - Average sum up till the previous partition.

Working

1. We’ll loop from i = START to i = (N - 1)^th position for every partition.
2. Now recurse from i + 1 and make K - 1 partition more.
3. BASE CASE - If K == 1 or START >= N, which means we only have to make one partition now or we are done partitioning, so we’ll calculate the average sum of the remaining element in the array and update the maximum average sum.

In the main function we’ll call largestSumOfAveragesRec()(N, ARR, START = 0, K, SUM = 0) and return MX_SUM.

Program

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

// Global variable to store the largest sum of averages.
double mx_sum;

// Function that tries every permutation of partitions and computes the maximum of the 'SUM'.
void largestSumOfAveragesRec(int n, vector<int> arr, int start, int k, double sum)
{
   // Initialize current partition sum.
   double sm = 0;
   
   // If it's the last partition, calculate its average sum and update the 'MX_SUM' value.
   if (k == 1 || start >= n)
   {
       // Finding the average sum of the last partition.
       for (int i = start; i < n; i++)
       {
           sm += arr[i];
       }
       sum += sm / (n - start);
       
       // Update 'MX_SUM' value.
       mx_sum = max(sum, mx_sum);
       
       return;
   }
   
   // Else try to divide the current partition in every possible way.
   for (int i = start; i < n - 1; i++)
   {
       sm += arr[i];
       
       // Call largestSumOfAveragesRec() for the next partition adding current partitions average sum to prev sum.
       largestSumOfAveragesRec(n, arr, i + 1, k - 1, sum + (sm / (i - start + 1)));
   }
}

// Function that returns the largest sum of averages.
double largestSumOfAverages(vector<int> &arr, int k)
{
   mx_sum = 0;
   
   // Call the recursive function.
   largestSumOfAveragesRec(arr.size(), arr, 0, k, 0);
   
   // Return largest sum of averages.
   return mx_sum;
}

int main()
{
   // Taking user input.
   int n, k;
   cout << "Enter the value of N: ";
   cin >> n;
   
   vector<int> arr(n);
   cout << "Enter the array elements: ";
   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }
   cout << "Enter the value of K: ";
   cin >> k;
   
   // Calling largestSumOfAverages() function.
   double largestSum = largestSumOfAverages(arr, k);
   cout << fixed << setprecision(6) << "Largest Sum of Averages is: " << largestSum << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the value of N: 10
Enter the array elements: 2 6 8 1 5 9 2 7 12 1
Enter the value of K: 3

Output

Largest Sum of Averages is: 18.900000

Time Complexity

O((N−1)*C*(K-1)), where ‘N’ is the size of the array, ‘K’ is the number of partitions to be made, and ‘C’ is the number of combinations = (N-1)!/(N-K)!*(K-1)!.

Space Complexity

O(K), where K is the number of partitions to be made.

Since there is only ‘K’ function calls in the recursion stack.

Check out Longest Common Substring

Approach 2- Dynamic Programming

The above problem has optimal substructure and overlapping problems. Hence we can solve it using dynamic programming.

ARR(i, K) = ARR(j, K - 1) + averageSum(i, j) 
(where averageSum (i, j) = ARR[i] +ARR[i + 1] +. . . + ARR[j - 1] / (j - i)).

• The best score partitioning ARR[i, N], i.e., partitioning the array from i to N into K parts, depends on ARR[j, N] (j > i), i.e., partitioning j to N into K - 1 parts.
• We can calculate the average sum efficiently by using the prefix sum.

averageSum(i, j) = prefixSum(j) - prefixSum(i) / (j - i).

• And since we don’t necessarily have to partition ARR(i, K) to initialize their values as averageSum(i, N).

Now let’s see how the algorithm works.

• Firstly, create a PREFIX_SUM array to store the prefix sum.
• Next, initialize the DP array and such that DP[i] = AVERAGE_SUM(i, N).
• Next, we loop from 0 to K and find the maximum of average sum at position i, making 0 to K partitions after it.

Program

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

// Function that returns largest sum of averages.
double largestSumOfAverages(vector<int> &v, int K)
{
   // Size of the array.
   int l = v.size();
   
   vector<double> prefixSum(l + 1);
   
   // Compute prefix sum, i.e., prefixSum[i] = v[0] + v[1] + . . . + v[i].
   for (int i = 0; i < l; ++i)
       prefixSum[i + 1] = prefixSum[i] + v[i];
       
   // Initializing the DP array.
   vector<double> dp(l);
   
   // Now, calculate the average sum using the prefix sum.
   for (int i = 0; i < l; ++i)
       dp[i] = (prefixSum[l] - prefixSum[i]) / (l - i);
       
   // Now try every partition.
   for (int k = 0; k < K - 1; ++k)
       for (int i = 0; i < l; ++i)
           for (int j = i + 1; j < l; ++j)
               dp[i] = max(dp[i], (prefixSum[j] - prefixSum[i]) / (j - i) + dp[j]);
               
   // Return DP[0].
   return dp[0];
}

int main()
{
   // Taking user input.
   int n, k;
   cout << "Enter the value of N: ";
   cin >> n;
   
   vector<int> arr(n);
   cout << "Enter the array elements: ";
   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }
   cout << "Enter the value of K: ";
   cin >> k;
   
   // Calling largestSumOfAverages() function.
   double largestSum = largestSumOfAverages(arr, k);
   cout << fixed << setprecision(6) << "Largest Sum of Averages is: " << largestSum << endl;

   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the value of N: 7
Enter the array elements: 10 42 71 32 12 41 53 
Enter the value of K: 4

Output

Largest Sum of Averages is: 178.333333

Time Complexity

O(K * N2), 'N' is the length of the array. 

In the largesSumOfAverages() function we run three nested loops. The first loop runs from 0 to K - 1. Both of the inner loops take O(N) time. Thus the overall time complexity is O( K * N * N), that is O(K * N2). 

Space Complexity

O( N ), ‘N’ is the length of the array.

We declare two arrays, ‘TEMP’ and ‘DP’ of size ‘N.’ Thus, the total auxiliary space required is O(N).

Key Takeaways

In this blog, we learned about an interesting problem, namely, the largest sum of averages. This question has been asked many times in coding interviews of leading product-based companies. We first saw a recursive approach and then optimized it using DP based on its characteristics of optimal substructure and overlapping subproblems. Stay tuned to learn more about such problems.

Check out this problem - Longest Subarray With Sum K 

Thanks, and Happy Coding!