1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Do you mean integers by "real numbers"? Examples are only integers here. Is it possible to take numbers like 0.1, 0.2 etc.? $\endgroup$ – Evil Sep 17 at 3:52
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W.♦ Sep 17 at 21:52
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Sep 17 at 22:09
-1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ $2+1+2>2\times 1\times 2$. $\endgroup$ – xskxzr Sep 17 at 4:08
  • $\begingroup$ There are no 0 in the question. $\endgroup$ – Evil Sep 17 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.