Post
by **chrismoh** » Tue Jan 22, 2002 5:54 pm

Ok, let's see...

we know that other than at zeroes, the absolute value of the multiple always increases. So we can store the maximal (absolute value) negative and positive product for that current subsequence (a subsequence started and ended by zeroes, for convenience it is always correct to place an arbitrary zero at the start and the end of the input sequence) - you have to of course reset whenever a 0 is encountered...

Of course, one has to deal with special cases such as no positive numbers in a sequence or subsequence...

and naturally this is assuming O(1) time for multiplying...

Here's an example to illustrate the traps faced by this algorithm:

consider the sequence

6 -6 -6 -7 8

At the start, greatest positive integer: 6, Negative: N/A

Next number: -6

Greatest positive integer, N/A

Negative, -36

Next number: -6

Greatest positive integer, 216

Negative, -6

Next number: -7

Greatest positive integer, 42

Negative, -1512

Next number: 8

Greatest positive integer, 336

Negative, -12096

And of course the answer is 336 for this example...

If the last number was 4, then the answer would be 216...