最大乘积子序列

Question

最大乘积子序列

algorithm

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)时间复杂度内实现？

- Shermano

1

由于您不需要代码，因此在Math.SE上可能更好。 - mwerschy

5

我不理解这个论坛，如果我询问代码，有人会告诉我它是错误的，并让我自己去做。如果我确实询问了代码，那也是错误的。 - Shermano

4

你知道吗，除非你已经知道问题的答案，否则你不能使用SO吗？;-)你能编辑你的回答并粘贴一下用来获得O(n^2)性能的代码吗？我不能保证O(n)，但我敢打赌我可以提供优化建议。 - FastAl

2

@Shermano，Stack Overflow是用于发布代码问题以确定代码有何问题和/或某些代码如何工作的（附加详细信息说明好问题和坏问题的内容）。它是Stack Exchange问答网站的一部分。由于您正在寻找算法，您可以像mwerschy所说的那样前往Math Stack Exchange网站，或者您可以前往Programmers Stack Exchange网站，在那里您可以获得概念性和算法性帮助（而不是关于代码本身的问题）。 - ajp15243

2

@ajp15243，真的吗？我的意思是，你说的话是错的。数学是用来做数学的，程序员是用来问关于职业和事物的问题的。算法问题在这里完全是切题的。 - unkulunkulu

显示剩余5条评论

2个回答

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)

- Paul Hankin

不错的简化！有一些小问题：它在[-3]处失败了。也许应该用第一个数字而不是0来初始化。prod(seq, a, lastneg)不应该是prod(seq, a, lastneg-1)吗？当a>b时，不应调用prod(seq, a, b)。请注意，溢出是真正的代码可能性。 - chux - Reinstate Monica

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chux - Reinstate Monica · Accepted Answer

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

如果所有的输入都是非0的且负数计数为偶数，则最大乘积还将通过将所有数字相乘找到。

因此，处理0和负数是需要工作的。

你需要遍历一次列表，并在遍历时计算累积乘积。如果你遇到了一个0，那么在该0之前的所有内容都是候选子集，它们的细节（起始索引，结束索引，乘积）需要保存起来，以防它比迄今为止找到的最佳结果更好。现在开始一个新的累积乘积。

如果你遇到一个负数，则该项是你累积总和的有条件断点。不使用负数的累积乘积将被评估为最佳。但现在你需要有两个累积乘积，一个是带有负数的，另一个是新的。因此，后续的乘法需要针对两个列表进行操作。此时，我会有两个累积乘积。如果你再遇到一个负数，则需要像之前描述的那样将每个运行列表拆分成两个。因此，如果不修剪，则可能会得到大量的运行列表。我认为你可以将运行列表修剪为仅跟踪3个：刚开始的子列表，具有奇数负数计数的持续列表和具有偶数负数计数的持续列表。在丢弃之前，需要评估任何非正在进行的乘法的候选子列表是否是最佳。

最后的时间复杂度是O(n)。