Максимальная подпоследовательность продукта

Question

Мне нужно найти максимальный продукт подпоследовательности в последовательности целых чисел n. Я ищу алгоритм, который не обязательно выражается в коде.

Пример:

1. В: 3,1, -2,4. Out: 4.
2. В: 2,5, -1, -2, -4. Out: 20. (2 * 5 * -1 * -2).

Я сделал алгоритм в O(n²), но теперь мне нужен один в O(n).
Я знаю, что это возможно.

Как это можно сделать в O(n)?

Answer 1

Если весь ваш вход был> 0, максимальный продукт будет найден путем умножения всех чисел вместе.

Если весь ваш вход был не равным 0 и имел четное количество отрицательных чисел, снова максимальный продукт будет найден путем умножения всех чисел вместе.

Таким образом, работа связана с нулями и отрицательными числами.

Вам нужно пройти через список один раз, вычислив запущенный продукт по мере его поступления. Если вы достигнете 0, то все, что до этого является подмножеством кандидата и его частями (начальный индекс, конечный индекс, продукт), нужно сохранить, если оно будет лучше, чем лучшее, что было найдено до сих пор. Теперь запустите новый запущенный продукт. Если вы достигли отрицательного числа, этот элемент является условным перерывом в вашей общей сумме. Бегущий продукт без использования отрицательного числа будет оценен в соответствии с вашими пожеланиями. Но теперь вам нужно иметь 2 работающих продукта, один с отрицательным числом и новый. Таким образом, последующие умножения должны работать против 2 списков. На данный момент у меня будет 2 работающих продукта. Если вы нажмете еще один отрицательный номер, каждый из ваших бегущих списков должен быть делит пополам, как описано выше. Таким образом, вы могли бы получить множество бегущих списков, если бы не обрезали. Я думаю, вы можете сократить списки, чтобы отслеживать только 3: подсписку, которая только что началась, продолжающийся список с нечетным числом отрицательных чисел и четным подсчетом отрицательных чисел. Любой дополнительный список кандидатов, не являющийся частью продолжающегося умножения, должен оценивать, чтобы он был лучшим, прежде чем его отбрасывать.

В конце его O (N)

Answer 2

Максимальная подпоследовательность продукт пробега ненулевых чисел является либо произведением всех чисел (если есть четное число отрицательных чисел), или это большее произведение всех чисел после первого отрицательного числа и произведение всех чисел до последнего отрицательного числа.

Это дает вам решение O (N): разбить последовательность на пробеги ненулевых чисел и применить правило в первом абзаце к каждому. Выберите максимальное значение.

C-подобный код Python для этого:

def prod(seq, a, b): 
    r = 1 
    for i in xrange(a, b): 
     r *= seq[i] 
    return r 

def maxprodnon0(seq, a, b): 
    firstneg = -1 
    negs = 0 
    for i in xrange(a, b): 
     if seq[i] >= 0: continue 
     negs += 1 
     if firstneg < 0: 
      firstneg = i 
     lastneg = i 
    if negs % 2 == 0: return prod(seq, a, b) 
    return max(prod(seq, firstneg + 1, b), prod(seq, a, lastneg)) 

def maxprod(seq): 
    best = 0 
    N = len(seq) 
    i = 0 
    while i < N: 
     while i < N and seq[i] == 0: 
      i += 1 
     j = i 
     while j < N and seq[j] != 0: 
      j += 1 
     best = max(best, maxprodnon0(seq, i, j)) 
     i = j 
    return best 

for case in [2,5,-1,-2,-4], [1,2,0,-4,5,6,0,7,1], [1,2,0,-4,5,6,-1,-1,0,7,1]: 
    print maxprod(case)