I don't think integer overflow is a causing the problem because when I changed the answer from an "int" to a "long long" (64 bits) I still got a wrong answer.

just solved the problem, got 320ms .. hmm.. big time
i tried with long long, but got WA
so i used strings got AC
(i wonder if anyone used just doubles or long llong, someone has a hint of "floats" in the solved rank list in pascal)
i think my algorithm is pretty fast using strings... still got big 320ms

anyway, konsept: read the program carefully, the answer in a input of A B C D could be
B C
you just did it straight forward to get the same output

the correct answer for ilham's input is:
95073783634185106058480752069956279199041805151309597685850804143872493687225762724265298696680866720060438572638872338185423558516745575068148747617495637233246533038583138313941279391299861732093898219130183367516764321276544576375955285875947586351401575501779450726582846893999985310435777036870171150461994629508009325776347750386998738990303339348062610266452782201995528321494110278961303062035131223129701746286517127149552121601906172064292436146016461554458887716864000000000000000000000000

hope it helps

Jorge Pinto

<font size=-1>[ This Message was edited by: Jorge Pinto on 2002-01-10 13:20 ]</font>

<font size=-1>[ This Message was edited by: Jorge Pinto on 2002-01-10 13:24 ]</font>

The crappy brute force solution is what I wrote 2 seconds after reading the problem, just as a "warm up". I have a much better algorithm now. (this might be what 'chrismoh' was mentioning, I dont' know)

Anyway, the basic idea is this:
if we keep track of the product of the first n numbers in the input (instead of just the nth number) then we can determine the product
of all numbers from i to j ( 1<=i,j<=n ) in constant time.
lets say the numbers are N[1],N[2],...N[n]. we dont store these numbers, instead we store:
P[1]=N[1]
P[2]=N[1]*N[2]
P[3]=N[1]*N[2]*N[3]
...
P[k]=P[k-1]*N[k]

now, observe that N*N[i+1]*N[i+2]*...N[j-1]*N[j]=P[j]/P[i-1].
so to find the product from i to j we need O(1) time instead of O(j-i+1).

hmmm... However, if you do it plainly like
that, you're program might be lot slower than
those using O(N^2) LCS since you must use Big
number routine many times. There's still one
more trick involved. This is when the "float"
thing takes place.

<font size=-1>[ This Message was edited by: Ilham Kurnia on 2002-01-11 09:20 ]</font>

i agree with ilham
the sort of dynamic program you are thinking is fine for int types, trying to do the multiplication just one time.
still, its * and / not + and -
put some big numbers multiplying and dividing
the implementation would be much harder and longer (time).. maybe just maybe you could win a few ms

not worth it, still a good algorithm for int's
i will use it if i find a similar problem with int's

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...