minmizing average problem

Question

Given a set containing N numbers, minimize the average where you can take out any string of consecutive numbers in the set. |N|<=100000

Ex. {5, 1, 7, 8, 2}

You can take out {1,7}, etc. but the way to minimize in this case is just to take out {7,8} which will give a minimum average of (5+2+1)/3=2.667.

NOTE:-You can't use the first or last one, so you can't take out {5} or {2}. I want to know the general procedure to minimize this. I am looking for a linear solution. thanks

Answer 1

Build a $2$-dimensional table, with each cell $[i][j]$ indicating the sum of elements $i,i+1,\dots,j$:

n = array.length
table[0][0] = array[0]
for j = 1 to n-1:
    table[0][j] = table[0][j-1]+array[j]
for i = 1 to n-1:
    for j = i to n-1:
        table[i][j] = table[i-1][j-1]-array[i]+array[j]

Then, find the indexes (other than first and last) of the cell with the largest value:

max = array[1][1]
max_i = 1
max_j = 1
for i = 1 to n-2:
    for j = i to n-2:
        if max < table[i][j]:
            max = table[i][j]
            max_i = i
            max_j = j
return max_i,max_j

Given a set of $n$ elements, time complexity and space complexity are both $O(n^2)$.

Answer 2

The average is minimized by taking only the smallest value in the set, i.e. take out the largest elements.

By the restriction of first/last element and consecutive string, you would take out the consecutive inner string which has the biggest weighted average (stringlength/n*stringaverage) and bigger than the weighted average of first and last element (2/n*firstlastaverage).