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

$\endgroup$
3
  • 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, 2019 at 3:52
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W.
    Sep 17, 2019 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$ Sep 17, 2019 at 22:09

2 Answers 2

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

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

By using dynamic programming, we can solve this! Negative values also work.

Let's start off with the subproblems. We would like to know $OPT(i,j)$, the maximum value of a consecutive subsequence from index $i$ to index $j$.

Then the recurrence equation looks like this:

$$ \begin{equation} OPT(i,j)=\begin{cases} v_i & \text{if $i=j$,}\\ \max \{ OPT(i,k) * OPT(k + 1,j), OPT(i,k) + OPT(k + 1,j) \mid i \le k \lt j \} & \text{else}. \end{cases} \end{equation} $$ The base case takes care of returning the value at index $i$ itself. If $i \neq j$, we split the substring into two parts at index $k$. We either take the product of the maximum values of those two parts, or we take the sum of them.

Now for the original problem, we have $OPT(0, n-1)$.

The order is guaranteed, since the problem is split up into smaller subproblems from left to right, until no subproblem can be found.

The time complexity of this algorithm with memorization can at most be the time it takes per subproblem = $O(n)$, and the amount of times we call this, $O(n)$. So $T(n) = O(n^2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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