Maximum average value of continuous interval

Given an array A, And length Len;
Choose a length >= Len The range of [l, r], Its average value is the largest .

$$ans=\frac{{\sum }_{i=l}^{r}A[i]}{r-l+1}$$

namely , The denominator The smaller it is , molecular The bigger it is . The better .

---

such as : A = [100, 1, 100], Len = 2
[100, 1] and [1, 100] All are 50.5;
[100, 1, 100] It's the biggest

---

First, look at a wrong idea .

Sweep code r Endpoint , Calculate with r For the right endpoint , Maximum .

such as , We have got r-1 For the right endpoint , The largest interval is : [l, r-1]; Assuming the current r The maximum interval of the endpoint is : [ll, r] ( Of course, the length of these two intervals is >= Len Of )
that , Can they deduce ?

First , ll >= l It is verifiable ; therefore , The left endpoint is monotonous ;

Algorithm : ( Calculation [l, r] Value and [l-1, r] Value , Compare ) ( If [l-1, r] Bigger , Then remove it. l-1) ( otherwise , [l, r] That's the answer. )

although , With r The maximum interval of the right endpoint , Its left endpoint is monotonous , namely : [l1, 1][l2, 2][l3, 3], …
There will be : l1 <= l2 <= l3
however , For a fixed right endpoint , Suppose the answer is [l, r], The answer to the previous interval is :[ll, r-1]
that , [ll, r][ll + 1, r][ll + 2, r] … Is it monotonous ??

Not really : [4, 3, 2, 1, 9]Len = 3]
The maximum interval of each right endpoint is : [4, 3, 2][4, 3, 2, 1][2, 1, 9]
about 9 Come on , [4, 3, 2, 1, 9] = 3.8, [3, 2, 1, 9] = 3.75, [2, 1, 9] = 4, It does not conform to monotony

---

The above algorithm , It seems to lead us into a very confused idea …

Mainly still , From the above equation , Both on the left Variable , It's all unknown ; therefore , under these circumstances , Rashly use greed , Is a bad choice .

From the above equation , If we scan unknown r, be r It is known. .
however : ( Left side ans It is unknown. ) ( On the right side of the molecular , The denominator All carry l, It's also unknown ), That is to say 2 A variable .
We are now , One must be eliminated ; l There are many options for endpoints , So choose to eliminate ans This variable .