Databases
StackOverflow2013
Postsdbo
POBuilding an expression with maximum value
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBuilding an expression with maximum value
    primarykey
    data
    text
    <p>Given <code>n</code> integers, is there an <code>O(n)</code> or <code>O(n log n)</code> algorithm that can compute the maximum value of a mathematical expression that can be obtained by inserting the operators <code>-</code>, <code>+</code>, <code>*</code> and parentheses between the given numbers? Assume only binary variants of the operators, so no unary minus, except before the first element if needed.</p> <p>For example, given <code>-3 -4 5</code>, we can build the expression <code>(-3) * (-4) * 5</code>, whose value is <code>60</code>, and maximum possible.</p> <p><strong>Background:</strong></p> <p>I stumbled upon this problem some time ago when studying genetic algorithms, and learned that it can be solved pretty simply with a classical genetic algorithm. This runs slowly however, and it's only simple in theory, as the code gets rather ugly in practice (evaluate the expression, check for correct placement of brackets etc.). What's more, we're not guaranteed to find the absolute maximum either.</p> <p>All these shortcomings of genetic algorithms got me wondering: since we can don't have to worry about division, is there a way to do this efficiently with a more classic approach, such as dynamic programming or a greedy strategy? </p> <p><strong>Update:</strong></p> <p>Here's an F# program that implements the DP solution proposed by @Keith Randall together with my improvement, which I wrote in a comment to his post. This is very inefficient, but I maintain that it's polynomial and has cubic complexity. It runs in a few seconds for ~50 element arrays. It would probably be faster if written in a fully imperative manner, as a lot of time is probably wasted on building and traversing lists.</p> <pre><code>open System open System.IO open System.Collections.Generic let Solve (arr : int array) = let memo = new Dictionary&lt;int * int * int, int&gt;() let rec Inner st dr last = if st = dr then arr.[st] else if memo.ContainsKey(st, dr, last) then memo.Item(st, dr, last) else match last with | 0 -&gt; memo.Add((st, dr, last), [ for i in [st .. dr - 1] do for j in 0 .. 2 do for k in 0 .. 2 do yield (Inner st i j) * (Inner (i + 1) dr k) ] |&gt; List.max) memo.Item(st, dr, last) | 1 -&gt; memo.Add((st, dr, last), [ for i in [st .. dr - 1] do for j in 0 .. 2 do for k in 0 .. 2 do yield (Inner st i j) + (Inner (i + 1) dr k) ] |&gt; List.max) memo.Item(st, dr, last) | 2 -&gt; memo.Add((st, dr, last), [ for i in [st .. dr - 1] do for j in 0 .. 2 do for k in 0 .. 2 do yield (Inner st i j) - (Inner (i + 1) dr k) ] |&gt; List.max) memo.Item(st, dr, last) let noFirst = [ for i in 0 .. 2 do yield Inner 0 (arr.Length - 1) i ] |&gt; List.max arr.[0] &lt;- -1 * arr.[0] memo.Clear() let yesFirst = [ for i in 0 .. 2 do yield Inner 0 (arr.Length - 1) i ] |&gt; List.max [noFirst; yesFirst] |&gt; List.max let _ = printfn "%d" &lt;| Solve [|-10; 10; -10|] printfn "%d" &lt;| Solve [|2; -2; -1|] printfn "%d" &lt;| Solve [|-5; -3; -2; 0; 1; -1; -1; 6|] printfn "%d" &lt;| Solve [|-5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6;|] </code></pre> <p>Results:</p> <blockquote> <p>1000<br> 6<br> 540<br> 2147376354 </p> </blockquote> <p>The last one is most likely an error due to overflow, I'm just trying to show that a relatively big test runs too fast for this to be exponential.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USRuss Clarke
    1. USIVlad
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POBuilding an expression with maximum value
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POBuilding an expression with maximum value
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POBuilding an expression with maximum value
      1. USSheldon L. Cooper
      1. VTFavorite
    1. COInitial thoughts - addition / subtraction seems like they'll be rarely used in a solution - multiplication will be the predominant operator used, with + / - used to deal with 1's in the input set (as * 1 is useless!) and to cope with the case where you have an odd number of negative values - where simple multiplication-of-all-values will result in a -ve.
      singulars
      1. POBuilding an expression with maximum value
      1. USWill A
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload