# Algorithm for finding largest subset with equal number of even and odd elements

A sequence of positive integers $a_1, ..., a_n$ is given. Compute the length of the largest continuous subsequence such that the number of even integers is equal to the number of odd integers in the subsequence.

I have thought that we could take all those integers mod 2 and store those in an array, then take two pointers $i=0,j=n-1$ and somehow sweep the table until #(even) = #(odd) is found in the subsequence inside, so that $j-i+1$ would be the optimal length. But I don't know how exactly to choose which of the two pointers to increase/decrease each time, so that I get an $O(n)$ algorithm.

Is my algorithm on the track, or can't it be used here? What algorithm do I need to apply and how can I think of its idea? (It would be preferable if this problem could be solved without using special data structures, such as AVL, segment, suffix trees, etc.)

Here's an easy linear time solution which uses $O(n)$ space. You could probably bring this down to $O(1)$ space using the techniques you mentioned.
First compute $$D_i = \# \text{even integers among a_1,\ldots,a_i} - \# \text{odd integers among a_1,\ldots,a_i}.$$ You can do this in $O(n)$.
Second, for each $\Delta \in \{-n,\ldots,n\}$, compute $a_\Delta = \min \{ i : D_i = \Delta \}$ and $b_\Delta = \max \{ i : D_i = \Delta \}$ (possibly these are undefined). You can do this in $O(n)$.
Finally, compute $\max_\Delta b_\Delta - a_\Delta$ for all $\Delta$ for which these indices exist. This also takes $O(n)$.
• I really don't fully understand that algorithm... Can you rephrase it somehow please? First, what does "integers among first i" mean? Also, $a_Δ$ is an index, so $Δ$ is a subindex? And finally, by finding this maximum, what exactly is accomplished?