Algorithm for finding largest subset with equal number of even and odd elements
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)$.