Максимальний добуток#155

Максимальний добуток (Editorial)

Оскільки |A_i| \le 2, кожен елемент належить множині \{-2, -1, 0, 1, 2\}. Це різко спрощує задачу: модуль добутку дорівнює 2^{(\text{кількість елементів } \pm 2)}, а знак визначається парністю кількості від'ємних елементів.

Спочатку розіб'ємо масив нулями на максимальні відрізки без нулів — будь-який відрізок, що містить нуль, дає добуток нуль.

Розглянемо один такий відрізок. Якщо кількість від'ємних елементів у ньому парна, добуток додатний, і брати треба весь відрізок — більше двійок уже не набрати.

Якщо ж кількість від'ємних непарна, доведеться відкинути частину відрізка так, щоб позбутися рівно одного від'ємного числа. Це можна зробити лише двома способами: викинути префікс до першого від'ємного включно або суфікс від останнього від'ємного включно. З цих двох варіантів обираємо той, у якому залишилось більше елементів .

Порівнюємо найкращі варіанти з усіх відрізків за кількістю двійок і запам'ятовуємо межі. Окремо не забудьте про кандидата з добутком нуль: якщо в масиві є нуль, а всі додатні варіанти дають добуток менший за одиницю (наприклад, коли кожен зеро-відрізок складається з одного від'ємного числа), відповіддю може бути саме одна нульова клітинка.

Складність — , достатньо одного проходу з підрахунком позицій від'ємних елементів у поточному відрізку. Виводити треба межі і , а не сам добуток — він може бути астрономічно великим.