Maximum Product Subsequence

Question

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

Example:

• B: 3.1, -2.4. Out: 4.
• B: 2.5, -1, -2, -4. Out: 20. (2 * 5 * -1 * -2).

I executed the algorithm in O(n²) , but now I need one in O(n) .
I know this is possible.

How can this be done in O(n) ?

Answer 1

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

If your entire input was not equal to 0 and had an even number of negative numbers, again the maximum product will be found by multiplying all the numbers together.

So, the work is related to zeros and negative numbers.

You need to go through the list once, calculating the launched product as it arrives. If you reach 0, then everything that previously is a subset of the candidate and its parts (initial index, final index, product) must be preserved if it is better than the best that has been found so far. Now launch a new launched product. If you reach a negative number, this item is a conditional break in your total. A running product without using a negative number will be rated at its best. But now you need to have 2 working products, one with a negative number and a new one. Thus, subsequent multiplications should work against 2 lists. At the moment I will have 2 working products. If you click another negative number, each of your scrolling lists should be halved, as described above. That way you could get a lot of creeping lists if you hadn't cropped. I think you can shorten the lists to track only 3: the sublist that has just begun, an ongoing list with an odd number of negative numbers and an even count of negative numbers. Any sub-candidate list that is not part of ongoing multiplication must be evaluated to see what is best before dropping it.

At the end of it is O (n)

Answer 2

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

This gives you an O (N) solution: break the sequence into runs of nonzero numbers and apply the rule in the first paragraph to each. Select the maximum value.

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)