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

Question

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

Answer 1

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

• user21069: 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?
• Yuval Filmus: I improved the notation slightly. The end result is the length of the largest contiguous subsequence having an equal number of odd and even integers. I leave the rest for you to ponder.