c++ - minimize average by taking out numbers -

given set of numbers, minimize average can take out string of consecutive numbers in set.

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

you can take out {1,7}, etc. way minimize in case take out {7,8}.

you can't use first or last one, can't take out {5} or {5,1}.

here's bashing inefficient code

#include <iostream> #include <fstream> #include <iomanip> #define max_n 100000 using namespace std;  int n, numbers[max_n], sum, curr_sum; double average, curr_average, minimum = 10000;  int main() {     cin >> n;     for(int i=0;i<n;i++)     {        cin >> numbers[i];        sum+=numbers[i];      }      average = (double) sum/n; 

then iterate through every possible pair

1. you want discard every number larger or equal max(first,last).
2. you want keep every number lesser min(first, last).
3. you need decide whether keep numbers < min(first, last) ; max(first, last) ).

satisfying 1. , 2. easy, harder decide 3. there comes math. a sum of first number, last number , numbers satisfying 2. r sum of remaining numbers (after throwing out 1.). can write following equation:

a+r         ---- = p + ---- n+m         n 

when n quantity of numbers in a, while m quantity of numbers in r, p difference between average containing numbers r , 1 without them. solve p:

     nr - p = ----------      n( n+m ) 

since n , a constant, have 2 variables - m , r. don't division unless nr - am negative, since want p make average lesser, not bigger or equal, right? , division waste of time. throw largest number r consists of, decrease m. stop on r or m equal 0. return p + a/n (you have store minimal p somewhere, right?).

i think there's no reason should code - skills presented writing above code sufficient write idea behind post.

maybe has better, sub-linear algorithm finding minimal average task.