Largest Sum of Averages

Author Husen Kagdi

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

Yusuf works at Amazon. He will be visiting his college to conduct a placement drive. He is selecting the problems to be asked in the interview. So he found this interesting problem, namely, the Largest sum of averages. It is based on arrays and dynamic programming topics. So let us discuss the problem and discuss various solutions possible to solve it.

Problem Statement

Given an array and an integer K. We need to partition the array into atmost K non-empty adjacent subarrays. The score of a partition is the sum of averages of each of the subarrays. Note that the partition must use every integer in an array and that the score is not necessarily an integer. Return the maximum score that you can achieve of all possible partitions.

Input

[9, 1, 2, 3, 9], K=3.

The best choice to partition the array is [9], [1, 2, 3], and [9]. Thus the sum of averages is 9 / 1 + (1 + 2 + 3)/3 + 9 / 1 = 20.000000. Note that there are many ways to partition the array but this is the most optimal partition.

Output

20.000000

Approach

Answers to partitioning A[j:] (j > I into fewer pieces determine the best score partitioning A[i:] into at most K parts. Because the states constitute a directed acyclic graph, we may apply dynamic programming.

Algorithm

Let the highest score for partitioning A[i:] into as many sections as possible be dp(i, k). If the first set of A[i:] partitions terminates before j, then our candidate partition has a score of average(i, j) + dp(j, k-1), where average(i, j) = (A[i] + A[i+1] +... + A[j-1]) / (j - I) (floating point division). We choose the one with the greatest score, remembering that we don't have to partition dp(i, k) if we don't want to (i, N). Our recursion in the larger circumstance is: dp(i, k) = max(average(i, N), max j > i(average(i, j) + dp(j, k-1)). We can calculate averages a little faster if we know prefix sums.If P[x+1] = A[0] + A[1] +... + A[x], average(i, j) = (P[j] - P[i]) / (P[j] - P[i]) / (P[j] - P[i]) / (P[j] - P[i]) / (P[j] - P[i]) / (P[j] - P[i]) (j - i). Our approach to dp is based on a "bottom-up" methodology. In our outer-most loop, at loop number k, we're calculating the next layer dp(i, k+1), where dp[i] represents dp(i, k) from the preceding discussion. The inner-most loop computes max j > i(average(i, j) + dp(j, k)), and the end of our second loop computes I = 0. N-1 denotes the end of the process of determining the correct value for dp (i, t).

Code

#include<iostream>
#include<vector>
using namespace std;
double largestSumOfAverages(vector<int>& v, int K) {
int l = v.size();
vector<double> temp(l+1);
for (int i = 0; i < l; ++i)
temp[i+1] = temp[i] + v[i];

vector<double> dp(l);
for (int i = 0; i < l; ++i)
dp[i] = (temp[l] - temp[i]) / (l - i);

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], (temp[j]-temp[i]) / (j-i) + dp[j]);

  return dp[0];
}
int main(){
int N;
cin>>N;
vector<int> v(N);
for(int i=0; i<N; i++){
  cin>>v[i];
}
int K;
cin>>K;
cout<<largestSumOfAverages(v, K);
return 0;
}

Input

9 1 2 3 9

Output

20.000000

Time Complexity

O( K * N2 ), N is 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, it takes O( N ) time.

Check out Longest Common Substring

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 MNCs. Thus it is very important. The time complexity of our algorithm is O( K * N2 ), N is length of the array. Stay tuned to learn more about such problems.

Check out this problem - Longest Subarray With Sum K

Happy Coding!