Maximum product subsequence [closed]

Question

I need to find the maximum product of a subsequence in sequence of n integers. I'm looking for an algorithm, not necessarily expressed as code.

Example:

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

I've done an algorithm in O(n²), but now I need one in O(n).
I know that it's possible.

How can this be done in O(n)?

Answer 1

If all your input was > 0, the maximum product would be found by multiplying all numbers together.

If all your input was non-0 and had an even count of negative numbers, again the maximum product would be found by multiplying all numbers together.

So the work is in dealing with zeros and negative numbers.

You need to through the list once, computing the running product as you go. If you reach a 0, then everything before that is a candidate subset and its particulars (start index, end index, product) needs to be saved should it be better than the best so far found. Now start a new running product. If you reach a negative number, that item is a conditional break in your running total. The running product without using the negative number would be assessed to your best. But now you need to have 2 running products, the one with the negative number and a new one. Thus subsequent multiplies need to work against 2 lists. At this point I would have 2 running products. Should you hit another negative number, each of your running list need to bisect as described beforehand. So you could end up with lots of running lists if you did not prune. I think you can prune the running lists to only keep track of 3: the sublist that just started, the continuing list with odd count of negative numbers and an even odd count of negative numbers. Any candidate sub-list not part of the ongoing multiplication should be assesses to see it is the best before dropping it.

At the end its O(n)

Answer 2

The maximum subsequence product of a run of non-zero numbers is either the product of all the numbers (if there's an even number of negative numbers), or it's the greater of the product of all the numbers after the first negative number, and the product of all the numbers up to the last negative number.

This gives you an O(N) solution: break the sequence into runs of non-zero numbers and apply the rule in the first paragraph to each. Pick the max of these.

C-like Python code for this:

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)