Define digit parity of a number as the parity of the sum of digits of the number. Let $a_1,a_2,\ldots,a_{100}$ be a rearranged sequence. We claim that $a_k$ and $a_{k+10}$ cannot both remain on their places. There are 10 terms between them. Note that the digit parity of consecutive terms must be different. So there must be an odd number of terms between $a_k$ and $a_{k+10}$, contradiction. Therefore at most one of each pair $(0,10),(1,11),(2,12),\ldots,(89,99)$ remain on its place. The answer is at most 50. The following arrangement show that 50 is indeed the maximum: 00,01,02,03,04,05,06,07,08,09, 19,18,17,16,15,14,13,12,11,11, 20,21,22,23,24,25,26,27,28,29, 39,38,37,36,35,34,33,32,31,30, 40,41,42,43,44,45,46,47,48,49, 59,58,57,56,55,54,53,52,51,50 60,61,62,63,64,65,66,67,68,69, 79,78,77,76,75,74,73,72,71,70, 80,81,82,83,84,85,86,87,88,89, 99,98,97,96,95,94,93,92,91,90.