How to compute the min average sub-array better than O(n^2)? [duplicate]

Question

I wrote the following to compute the minimum start index of the sub-array (with minimum two elements) whose average is minimum.

However, can't figure out a way how to make it faster, namely, a O(n) or O(n log n) way. I can't think of any way to "visit" all the possible sub-arrays without hitting O(n^2):

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

int solution(vector<int> &A) {
    float previousAvg = 0.0;
    float minAvg = numeric_limits<float>::max();
    int minStartIx = numeric_limits<int>::max();
    for (size_t i = 0; i < A.size(); ++i) {
        for (size_t j = i + 1; j < A.size(); ++j) {
            if (j == i + 1) {
                previousAvg = (A[i] + A[j]) / 2.0;
                cout << "avg(from=" << i << ", to=" << j << ") = " << previousAvg << endl;
            } else {
                previousAvg = (previousAvg * (j - i) + A[j]) / (j - i + 1);
                cout << "avg(from=" << i << ", to=" << j << ") = " << previousAvg << endl;
            }
            if (previousAvg < minAvg) {
                minAvg = previousAvg;
                minStartIx = i;
            }
        }
    }
    return minStartIx;
}

int main() {
    vector<int> A = {4, 2, 2, 5, 1, 5, 8};
    cout << solution(A) << " must equal to 1" << endl;
    return 0;
}

and with logging it produces the correct output:

avg(from=0, to=1) = 3
avg(from=0, to=2) = 2.66667
avg(from=0, to=3) = 3.25
avg(from=0, to=4) = 2.8
avg(from=0, to=5) = 3.16667
avg(from=0, to=6) = 3.85714
avg(from=1, to=2) = 2
avg(from=1, to=3) = 3
avg(from=1, to=4) = 2.5
avg(from=1, to=5) = 3
avg(from=1, to=6) = 3.83333
avg(from=2, to=3) = 3.5
avg(from=2, to=4) = 2.66667
avg(from=2, to=5) = 3.25
avg(from=2, to=6) = 4.2
avg(from=3, to=4) = 3
avg(from=3, to=5) = 3.66667
avg(from=3, to=6) = 4.75
avg(from=4, to=5) = 3
avg(from=4, to=6) = 4.66667
avg(from=5, to=6) = 6.5
1 must equal to 1

Answer 1

Based on references here, I tried to word my own understanding.

If we split a (contiguous) subarray in two, one with average a and length n and the other with average b and length m, we have two possibilities:

(1) the two averages are equal, in which case the average for the whole subarray is the same as a and b:

  (an + bm) / (n + m)
= (an + am) / (n + m) (a equals b)
= a(n + m) / (n + m)
= a
= b

(2) one average is smaller than the other, in which case it's also smaller than the average of the whole subarray:

(Averages a and b)
a < b
(an + bm) / (n + m) > a (the average of the whole is greater than a's)
an + bm > a(n + m)
an + bm > an + am (since b > a) 

Now imagine we are looking at one of the subarrays that has the minimum average and has more than three elements. While parts have equal averages, split each part recursively; according to the logic above, parts must have equal averages or we would have a contradiction since we assumed the average for the whole subarray is the minimum. Eventually, we will find subarrays that have either two or three elements. Since we started with a (larger) subarray that had the minimum average, the two- or three-element subarray components must also have that same minimum average.

This proves that the largest window we need to examine is of three elements. The smallest is of two elements since that's our minimum length. O(n).