How to compute function rolling averages maximum for each possible interval length?
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))