0

So I came across this question earlier, and I'm stumped: When given a list of n integers, we are looking to return a value equal to the highest possible average of x consecutive integers in that list.

For example:

we have list [1, 2, 1, 7, 9, 8, 3, 2]

we have x = 3

our answer would be 8, because the sequence of 3 consecutive integers, with the highest average, is 7, 9, 8, and their average is 8.

[1, 2, 1, 7, 9, 8, 3, 2]

Anyone know how to approach this in code/pseudocode?

user313
  • 681
  • 1
  • 8
  • 21

2 Answers2

3

Just have a sliding window of x and look for the maximum. The comments in the code should be self explanatory.

Note : Be careful while adding numbers they could be very large or your x is very high that you could run into overflow after adding numbers without dividing by x. So divide by x each time you add to sum.

double sum = 0;
for ( int i = 0; i < x; i++ ) {
   sum += (double) ( arr[i] ) / x; //calculate the average of first `x` numbers, if your input elements are integers you need to cast it to double.
}
double max = sum; //initialize a variable that has that value which you will maximize
for ( int i = x; i < n; i++ ) {
  sum -= (double)( arr[i-x] ) / x; //leave the first in the x elements
  sum += (double)( arr[i] ) / x; // add the current element so you always compute average of `x` elements.
  max = Math.max( max, sum ); //maximize max
}

return max;
SomeDude
  • 13,876
  • 5
  • 21
  • 44
  • 2
    If we are sure we won't run into datatype overflow issues we might as well compute the largest `x` consecutive numbers instead of averaging everytime – thebenman Oct 23 '18 at 03:55
  • Shouldn't it be better solved using Dynamic Programming, etc.? Just curious! – Failed Scientist Oct 23 '18 at 05:29
  • @thebenman if we are sure we are not going to overflow issues, yes just compute the sum of x consecutive numbers every time. that's ok. The problem should state clearly what is the maximum value that the input contains. – SomeDude Oct 23 '18 at 13:43
  • @FailedScientist why would be dynamic programming better? do you see any subproblems that can be solved and used to solve the bigger problem? – SomeDude Oct 23 '18 at 13:44
  • @SomeDude My point is if we have the max sum over `x` consecutive number we can still compute the highest average by just dividing it by `x` outside the for loop just once. – thebenman Oct 24 '18 at 03:33
2

You're looking for a sliding window average. Basically, you calculate the average for each of the possible sub-arrays of x length. You'd start with a window of indices 0 to (x-1), then go to 1 to x, then 2 to (x+1) and so on, calculating the average of each window. If the average of current window is greater than the average of previous window, you update your max average.

Kon
  • 4,023
  • 4
  • 24
  • 38