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

## 1 Answer

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? – Jason Dec 18 '16 at 20:36
• 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. – Yuval Filmus Dec 18 '16 at 20:41