количество подмассивов, чье произведение четное?

Question

для массива размером n, n <= 10 ^ 5, каков эффективный подход для подсчета количества подмассивов, чье произведение четное? я использую наивный подход с (на ^ 3) сложность времени? пожалуйста, предложите какой-нибудь эффективный подход? </p>

Answer 1

Будьте осторожны: из вашего объяснения у меня сложилось впечатление, что вы берете все подмассивы, рассчитываете произведение и проверяете, является ли оно четным.

Однако есть одно очень важное математическое правило: когда у вас есть серии натуральных чисел, как только есть одно четное число, продукт будет четным.

Итак, я бы посоветовал вам запрограммировать следующий алгоритм:

1. Поиск в вашем массиве для четного числа.
2. Подсчет количества подмассивов, содержащих это четное число.
3. Поиск в вашем массиве следующего четного числа.
4. Подсчет количества подмассивы, содержащие следующее четное число, но не содержащие предыдущего четного числа.
5. Продолжайте, пока не обработаете все четные числа в вашем массиве.