Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
3.
Approach
4.
Algorithm
5.
Code
5.1.
Input
5.2.
Output
5.3.
Time Complexity
5.4.
Space Complexity
6.
Key Takeaways
Last Updated: Mar 27, 2024

Largest Sum of Averages

Author Husen Kagdi
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

Also Read, Byte Array to String

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

Previous article
Longest Increasing Subsequence | Part 2
Next article
Interleaving Strings
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass