Для начала осознаем, что максимальную последовательность Рик получит, если колода будет отсортирована в возрастающем порядке. Действительно, так как по условию требовалось, чтобы числа на карточках были в возрастающем порядке, любая последовательность подходящая под условие является подпоследовательностью отсортированной колоды.
Пусть после сортировки получится так, что все соседние карточки разной четности. В таком случае ответ будет равен размеру колоды. Теперь рассмотрим ситуацию, в которой две соседние карточки имеют одинаковую четность. Так как, как минимум одна из них не войдет в наибольшую последовательность, мы можем убрать из них и решить задачу для оставшейся колоды, так как для нее ответ будет такой же.
Реализация будет довольно простой и не будет требовать удаления из середины. Мы будем поддерживать массив, в котором будем хранить ответ, изначально положим туда минимальное число из колоды. Затем последовательно пройдемся по колоде, и если текущее число, отличается по четности от последнего взятого в ответ числа, возьмем его тоже. Остается только вывести размер получившегося ответа.
Суммарное время этого алгоритма или O(n2 + n), в зависимости от того, какую сортировку использует решение.