# How can I calculate the maximum sum/product of sequence?

I am looking for an algorithm in $$O(N^2)$$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $$\{ 1, 2, 3 , 4\}$$) by inserting a plus ($$+$$) or multiplication ($$\times$$) between the elements.

Really not having much luck and wondering if anyone has any insight on this?

It must follow normal order of precedence.

For example with $$\{1,2,3,4\}$$, the maximum is $$1+2\times3\times4 = 25$$ not $$1\times2\times3\times4 = 24$$ and not $$1\times2+3+4 = 9$$.

• Do you mean integers by "real numbers"? Examples are only integers here. Is it possible to take numbers like 0.1, 0.2 etc.? – Evil Sep 17 at 3:52
• cs.stackexchange.com/tags/dynamic-programming/info – D.W. Sep 17 at 21:52
• Hint: For given $i, j \le N$, see if you can compute the maximum value that can be obtained from just the first $j$ elements by inserting $+$ or $\times$ between them, with the additional restriction that the last $i$ operations consist of a $+$ followed by $i-1$ $\times$s. – j_random_hacker Sep 17 at 22:09

Let's say all numbers are positive (i.e. $$\geq0$$). Before and after $$0$$s you should always use $$+$$. This could also solved in $$O(n^2)$$ by first finding all zeros and then find maximum value for each group separated by zeros. Inside each group, for positive numbers, you should always use $$\times$$ except in $$1$$ cases, if ones are in the middle of a group, still you should choose $$\times$$. But when ones are at the very beginning or at the very end of the group, you should choose $$+$$.
• $2+1+2>2\times 1\times 2$. – xskxzr Sep 17 at 4:08