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&lt;i&lt;T-k} {\frac{1}{k} \sum_{j=i}^{i+k} f(j)}$$

for $ 0&lt;k \le T $ given some discrete function $f$ defined on $ [0; T]$. 

Is there algorithm to do it faster then naive $O(n^2)$? If so, how?
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))