Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
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 $+$.
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)$.
