Efficient evaluation of this correlation measure What do you think would be the most efficient way of evaluating the following expression?
Given a binary sequence $ E_N = (e_1,...,e_N) \in  \{  -1,+1   \}^N $, and for $D = (d_1,d_2)$ with non-negative integers $0 \leq d_1 < d_2 $.
Evaluate $$\max_{M,D} \lvert \sum_{n = 1}^M e_{n+d_1}  e_{n+d_2}  \lvert ,$$ where
the maximum is taken over all $D = (d_1, d_2)$ and $M$ such that $ 0 \leq d_1 < d_2  < M+d_2 \leq N $
My algorithm seems to be $ O(n^4) $, but it certainly could do better.
 A: Let's change slightly the definition of your sum:
$$\max_{d_1, d_2, M} \left| \sum_{n=d_1+1}^{d_1+M}e_n e_{n+d_2-d_1}\right|$$
s.t. $d_2-d_1 > 0$, $1 \le M \le N-d_2$.
So with $\Delta=d_2-d_1$ this is equal to:
$$\max_{\Delta, l, r} \left| \sum_{n=l}^{r}e_n e_{n+\Delta}\right|$$
s.t. $\Delta > 0$ and $1 \le l \le r \le N-\Delta$.
Let's compute it in $\Theta(N^2\log N)$.


*

*Compute $a_{\Delta}(i)=e_i e_{i+\Delta}$ for all $i, \Delta$ in $\Theta(N^2)$.

*Compute the prefix sum $A_{\Delta}(i)=\sum_{k=1}^{i-1}a_{\Delta}(k)$ in $\Theta(N^2)$. Now you have an oracle which answers in $\Theta(1)$ to queries of the form "given $a$ and $b$, what is $\sum_{k=a}^{b}a_{\Delta}(k)$?".

*Initialize the answer to $-\infty$. Now loop over all $\Delta$, and for each of them:


*

*Initially insert in some data structure $S$. that allows you to insert, delete and find minimum and maximum (e.g. two binary search trees) all $A_\Delta(r+1)$ for all $1 \le r \le N-\Delta$. 

*For each $l$, find the minimum $A_\Delta(r+1)$ and the maximum $A_\Delta(r'+1)$ in $S$. Relax the answer with $|A_{\Delta}(r+1)-A_{\Delta}(l)$ and $|A_\Delta(r'+1)-A_\Delta(l)|$. Finally, delete $A_\Delta(l)$ from $S$.



The $O(\log n)$ factor overhead comes from the operations of $S$, which are probably logarithmic (e.g. if you use BSTs).

Actually it is possible to reduce this complexity to $\Theta(n^2)$, without using any complex data structure. Let's note we don't use the full potential of BSTs, because we only insert elements in the initial step (which is in some sort an offline query).
In our algorithm, we only need elements $A_\Delta(r)$ which are greater (or smaller) than $A_\Delta(s)$ for all $s>r$ (otherwise, the maximum/minimum won't change). Computing this list can be done in $\Theta(n)$. Then we don't need any BST in the third step, just update an index pointing to the current maximum/minimum element. When the maximal/minimal element is deleted, just use the previously built list to compute the next one.
