Как эффективно решить проблему подмассива максимального продукта в Python? ⇐ Python

[Anonymous]

Я пытаюсь решить задачу подмассива максимального продукта, которая описывается следующим образом:
Для массива целых чисел (положительных, отрицательных или нулевых) найдите максимальный продукт любого непрерывного подмассива.
Пример:
Ввод: [-2, 6, -3, -10, 0, 2]
Вывод: 180
Объяснение: подмассив [6, -3, -10] дает произведение 6 * -3 * -10 = 180.
Я пробовал перебирать массив, отслеживая текущих максимальных и минимальных продуктов, но я не понимаю, как поступать в случаях, когда появляется отрицательное число или ноль.

Код: Выделить всё

def maxProduct(arr):
max_ending_here = 0
min_ending_here = 0
max_so_far = 0

Не знаю, как обновить max_ending_here и min_ending_here для отрицательных чисел

Код: Выделить всё

    for num in arr:
pass  # Implementation goes here

return max_so_far

`
`Вопросы:

• Как мне следует обрабатывать переход при обнаружении отрицательного числа или нуля в массиве?
• Есть ли лучший способ решить эту проблему без явного рассмотрения всех возможных подмассивов (что потребовало бы O(n²) или более)?< /li>
  Какова оптимальная временная сложность решения этой задачи и как Могу ли я гарантировать, что мой подход достигнет этой цели?

Будем очень признательны за любые рекомендации и предложения. Спасибо!`

Подробнее здесь: https://stackoverflow.com/questions/792 ... -in-python