# How to compute function rolling averages maximum for each possible interval length?

I'm searching for a fast way to calculate

$$g(k):=\max_{0

for $$0 given some discrete function $$f$$ defined on $$[0; T]$$.

Is there algorithm to do it faster then naive $$O(n^2)$$? If so, how?

• Actually, your title contradicts to question text, so what you mean - max over all k faster than O(n^2) or max for given k? – Bulat Jul 16 '19 at 10:15
• Formula in question text is correct. I need max of rolling average for all possible k. in other words I need to calculate T values: each of those values is max value od rolling average of given length. – Artur Tadrała Jul 17 '19 at 13:05

• This will give me $O(n^2)$ if Im calculating for each possible k. – Artur Tadrała Jul 17 '19 at 13:07