7

我需要在序列中找到子序列的最大乘积n整数序列中找到子序列的最大乘积。我正在寻找一种算法，不一定表示为代码。

例子：

  1. 在：3,1,-2,4。出局：4。
  2. 在：2,5,-1,-2,-4。输出：20。（2*5*-1*-2）。

我已经在 中完成了一个算法O(n²)，但现在我需要一个在O(n).
我知道这是可能的。

如何做到这一点O(n)？

4

2 回答 2

5

如果您的所有输入都 > 0，则通过将所有数字相乘来找到最大乘积。

如果您的所有输入都是非 0 并且有偶数个负数，则通过将所有数字相乘可以再次找到最大乘积。

所以工作是处理零和负数。

您需要通过列表一次，计算正在运行的产品。如果您达到 0，那么在此之前的所有内容都是候选子集，如果它比目前找到的最好的要好，则需要保存其详细信息（开始索引、结束索引、产品）。现在开始一个新的运行产品。如果您达到负数，则该项目是您运行总数的有条件中断。不使用负数的运行产品将被评估为最好。但是现在您需要有 2 个正在运行的产品，一个带有负数的产品和一个新产品。因此，后续的乘法需要针对 2 个列表。在这一点上，我将有 2 个正在运行的产品。如果您遇到另一个负数，则您的每个运行列表都需要按照前面的描述进行平分。因此，如果您不进行修剪，您最终可能会得到很多运行列表。我认为您可以修剪运行列表以仅跟踪 3：刚刚开始的子列表、具有奇数负数和偶数奇数负数的连续列表。任何不属于正在进行的乘法的候选子列表都应该在删除之前进行评估，看看它是最好的。

最后它的 O(n)

于 2013-05-28T18:25:57.920 回答
3

一连串非零数的最大子序列乘积要么是所有数字的乘积（如果有偶数个负数），要么是第一个负数之后所有数字的乘积中的较大者，并且直到最后一个负数的所有数字的乘积。

这为您提供了 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)
于 2013-05-28T20:42:51.177 回答