Учитывая круговой массив из N целых чисел (то есть, A [0] и A [N - 1] смежны друг с другом), какое максимальное количество соседних пар, сумма которых четна, вы можете сформировать? Обратите внимание, что каждый элемент может принадлежать не более чем одной паре.
Например, если у нас есть [5, 7, 9, 6, 3], то вы должны соединить (5, 3) и (7, 9 ), чтобы получить ответ два. Кроме того, если у нас есть [1, 1, 1, 1, 1, 1], то ответ будет 3 (соедините каждый соседний элемент, не оборачиваясь вокруг него)
Это недавняя проблема, с которой я столкнулся во время интервью. , и я все еще не могу ее решить (я не получил работу). Я знаю, что сумма двух чисел с одинаковой четностью дает четную сумму (такую нечетную и нечетную, или четную и четную), но меня привлекает вся эта «циклическая» часть. В частности, я не могу понять, оптимально ли сочетать значение с его левым соседом или его правым соседом. Текущий алгоритм, о котором я думаю, выглядит следующим образом:
Для каждого индекса 0 <= i <= n - 1 попробуйте связать A [i] с A [i + 1 ], проверив их четность. </p>
Если оба A [0] и A [n-1] не являются парными в конце, объедините их в пару, если они имеют одинаковую четность.
Это неправильный алгоритм, поскольку он не работает для [1, 1, 1, 0, 1], и в этом случае оптимально объединить A [0] с A [n-1] и A [1] ] с A [2]. У кого-нибудь есть предложения? Я думал, возможно, что-то с программированием Dynami c, но я не уверен. Круглая часть меня действительно сбивает.
Спасибо.