Maximale Produktuntersequenz

Question

Ich muss das maximale Produkt einer Teilsequenz in der Reihenfolge von n ganzen Zahlen finden. Ich suche nach einem Algorithmus, nicht unbedingt als Code ausgedrückt.

Beispiel:

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

Ich habe einen Algorithmus in O(n²) gemacht, aber jetzt brauche ich einen in O(n).
Ich weiß, dass es möglich ist.

Wie kann dies in O(n) getan werden?

Answer 1

Wenn Ihre gesamte Eingabe> 0 ist, wird das maximale Produkt durch Multiplizieren aller Zahlen gefunden.

Wenn Ihre gesamte Eingabe nicht 0 ist und eine gerade Anzahl negativer Zahlen aufweist, wird das maximale Produkt wieder gefunden, indem alle Zahlen zusammen multipliziert werden.

Also ist die Arbeit im Umgang mit Nullen und negativen Zahlen.

Sie müssen einmal durch die Liste gehen und das laufende Produkt berechnen, während Sie gehen. Wenn Sie eine 0 erreichen, dann ist alles davor eine Kandidaten-Teilmenge und ihre Angaben (Startindex, Endindex, Produkt) müssen gespeichert werden, falls sie besser als die bisher beste ist. Starten Sie jetzt ein neues laufendes Produkt. Wenn Sie eine negative Zahl erreichen, handelt es sich um eine bedingte Pause in Ihrer laufenden Summe. Das laufende Produkt ohne die negative Nummer würde zu Ihrem besten bewertet werden. Aber jetzt müssen Sie 2 laufende Produkte haben, eine mit der negativen und eine neue Nummer. Folglich müssen nachfolgende Multiplikationen gegen 2 Listen arbeiten. An diesem Punkt hätte ich 2 laufende Produkte. Sollten Sie eine andere negative Zahl treffen, muss jede Ihrer Lauflisten wie zuvor beschrieben halbieren. Sie könnten also mit vielen laufenden Listen enden, wenn Sie nicht beschnitten haben. Ich denke, Sie können die laufenden Listen beschneiden, um nur 3 zu verfolgen: die gerade begonnene Unterliste, die fortlaufende Liste mit der ungeraden Anzahl negativer Zahlen und eine gerade ungerade Anzahl negativer Zahlen. Jede Kandidaten-Unterliste, die nicht Teil der laufenden Multiplikation ist, sollte so bewertet werden, dass sie die beste ist, bevor sie gelöscht wird.

Am Ende seiner O (n)

Answer 2

Das maximale Subsequenz Produkt einer Serie von Zahlen ungleich Null ist, entweder das Produkt aller Zahlen (wenn eine gerade Anzahl von negativen Zahlen es gibt), oder es ist die größer als das Produkt aller Zahlen nach der ersten negativen Zahl und das Produkt aller Zahlen bis zur letzten negativen Zahl.

Dies gibt Ihnen eine O (N) -Lösung: Brechen Sie die Sequenz in Läufe von Nicht-Null-Zahlen und wenden Sie die Regel im ersten Absatz auf jeden an. Wählen Sie die Max von diesen.

C-wie Python-Code für diese:

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)