最大的產品子序列

Question

我需要找到序列n整數的子序列的最大乘積。我正在尋找一種算法，不一定表示爲代碼。

實施例：

1. 在：3,1，-2,4。 Out：4.
2. In：2,5，-1，-2，-4。 Out：20.（2 * 5 * -1 * -2）。

我已經在O(n²)中完成了一個算法，但現在我需要一個在O(n)。
我知道這是可能的。

這怎麼能在O(n)？

Answer 1

如果你所有的輸入都大於0，最大的產品可以通過將所有數字相乘得到。

如果您所有的輸入都不是0，並且有負數的偶數，再次通過將所有數字相乘得到最大產品。

所以這項工作是在處理零和負數。

您需要通過列表一次，隨時計算正在運行的產品。 如果達到0，那麼在此之前的所有內容都是候選子集，如果它比迄今爲止找到的最好的子集更好，則需要保存它的詳細信息（開始索引，結束索引，產品）。現在開始一個新的運行產品。 如果你得到一個負數，那麼這個項目在你的跑步總數中是一個有條件的中斷。 未使用負數的正在運行的產品將被評估爲最佳狀態。但是現在你需要有兩個正在運行的產品，一個負數和一個新產品。因此後續的乘法需要針對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)