UVa 11059

From Algorithmist
Jump to navigation Jump to search

11059 - Maximum Product[edit]

icpcres.ecs.baylor.edu/onlinejudge/external/110/11059.html

Summary[edit]

Find the maximum positive product of consecutive elements S(i)*S(i+1)*...*S(j)} in a sequence of elements {S(1), S(2), ... , S(m)}. If all products are negative or 0, return 0.

Explanation[edit]

Brute force works nicely, due to generous time limits.

Quick and dirty implementation description for the beginner: If you can find the product of a sequence max_product_of_sequence(S, i, j) [breaking if element S(r) = 0 for some r, as this makes the product 0], you can simply maximise over these results. It can be noted that you need never look further than sequences j = 1,...,n and i=1,...,j.

Some slight (distribution-dependent) gains can be made at the input stage by bunching consecutive positive numbers in the sequence together in a single product.

Gotchas[edit]

The products can become larger than standard C++ integers. At most 18 numbers S(i) in a row, with -10 <= S(i) <= 10 can yield a maximal maximum product of 10^18. Note that return value is 0 for negative products (unsigned types can thus be used).

Solutions[edit]