I'm searching for a fast way to calculate

$$ g(k):=\max_{0<i<T-k} {\frac{1}{k} \sum_{j=i}^{i+k} f(j)}$$

for $ 0<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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Bulat Jul 16 '19 at 10:15
  • $\begingroup$ 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. $\endgroup$ – Artur Tadrała Jul 17 '19 at 13:05

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))

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.