# 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 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 at 13:05

## 1 Answer

The usual approach to compute rolling function is to keep/recompute old data and on each step "add" new data and subtract the data going out of the window. So, you need to transform your sum function into updateSum one:

sum(i+1) = updateSum(sum(i), f(i), f(i+k+1))

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