# Maximize order of operations [closed]

Here's a problem to which I don't know the answer. Suppose you have an ordered list of integers with an operator in between each consecutive pair. Let's restrict ourselves to three operations that are closed over the integers, namely addition, multiplication and subtraction. Is there a good way to find the order we should perform the operations such that the expression evaluates to the maximum value?

For example, given the input 5 * 5 - 3 + 8 * -2 the correct order is to first perform the addition leading to 5 * 5 - 11 * -2, then perform the last multiplication leading to 5 * 5 - -22, then perform the subtraction leading to 5 * 27, then perform the final multiplication giving 135, which is maximal.

The question is: does there exist a reasonably efficient way to find this answer? I can see some tricks that might help a little, but I can also see some roadblocks.

Here's a program in python that computes the solution in the dumb recursive O(2^n) fashion. It might be helpful to check answers.

def find_max(x):
if len(x) == 1:
return x[0]
y = [find_max(contract(x, i)) for i in xrange(len(x)//2)]
return max(y)

def contract(x, i):
return x[:2*i] + [do_op(*x[2*i:2*i + 3])] + x[2*i + 3:]

def do_op(left, op, right):
return {"+": left + right, "-": left - right, "*": left * right}[op]

init = [int(x) if i%2 == 0 else x for i,x in enumerate(raw_input().split())]
print find_max(init)


Usage: python findmax.py < in.txt where in.txt contains a sequence like 4 * -3 + 6 - 2 * 10.

Is there a significantly faster way?

• You could use dynamic programming to get some improvement. But does this belong here or on StackOverflow? Aug 26, 2011 at 11:43
• I'd say it belongs here as it's a programming puzzle. Aug 26, 2011 at 14:28
• From the FAQ: All questions on this site, whether a programming puzzle or a code golf, should have … An objective primary winning criterion, so that it is possible to indisputably decide which entry should win. Aug 26, 2011 at 14:47
• Your example is bad. After performing the addition (1st step), you should have 5 * 5 + 5 * -2. Aug 26, 2011 at 19:16
• @trinithis: I think Clueless had in mind 5 * 5 - (3 + 8) * -2 for the first addition step. Aug 26, 2011 at 19:32

import Data.Array

data Op = Plus | Minus | Times

exampleTerms :: [Integer]
exampleTerms = [5, 5, 3, 8, -2]

exampleOps :: [Op]
exampleOps = [Times, Minus, Plus, Times]

main = print $maximalOrder exampleTerms exampleOps type MinMax = (Integer, Integer) -- Given an operator and minimal/maximal values for left- and right-hand sides, -- compute the minimal/maximal value of the expressions joined together with this operator. combine :: Op -> MinMax -> MinMax -> MinMax combine Plus (lmin, lmax) (rmin, rmax) = (lmin + rmin, lmax + rmax) combine Minus (lmin, lmax) (rmin, rmax) = (lmin - rmax, lmax - rmin) combine Times (lmin, lmax) (rmin, rmax) = (minimum ps, maximum ps) where ps = [lmin * rmin, lmin * rmax, lmax * rmin, lmax * rmax] maximalOrder :: [Integer] -> [Op] -> Integer maximalOrder [] _ = error "maximalOrder: No terms" maximalOrder terms ops | length terms /= length ops + 1 = error "maximalOrder: Mismatched terms/ops lists." maximalOrder terms ops = snd$ minMax 0 (termCount - 1) where
termCount :: Int
termCount = length terms

termsA :: Array Int Integer
termsA = array (0, termCount-1) $zip [0..] terms opsA :: Array Int Op opsA = array (0, termCount-2)$ zip [0..] ops

dp :: Array (Int, Int) MinMax
dp = array ((0,0), (termCount-1,termCount-1))
[((start, end), minMax start end)
| start <- [0..termCount-1], end <- [start..termCount-1]]

minMax :: Int -> Int -> MinMax
minMax start end
| start == end =
let x = termsA ! start
in (x,x)
| otherwise =
let xs = [combine (opsA ! i) (dp ! (start,i)) (dp ! (i+1,end)) | i <- [start..end-1]]
in (minimum (map fst xs), maximum (map snd xs))


This computes the minimal and maximal values of every substring in the expression, by going through each intervening operator and finding the minimal/maximal result of treating that operator as the root of the expression. It collects these results into the overall minimal and maximal values for this substring.

This algorithm runs in O(n3) time and uses O(n2) space. Finding the minimal/maximal value of an expression string, once its substrings have been visited, takes O(len), where len is the length of the substring. The minimal/maximal value of every substring needs to be computed:

1..5
1..4 2..5
1..3 2..4 3..5
1..2 2..3 3..4 4..5
1..1 2..2 3..3 4..4 5..5


In this case, it takes 5*1 + 4*2 + 3*3 + 2*4 + 1*5. In general, the number of operations grows in a cubic fashion.

At the heart of the algorithm is the combine function, which takes an operator and the minimal/maximal values of each of its operands, and produces the minimal/maximal results.

To maximize the result:

• If adding two numbers, maximize both arguments.

• If subtracting two numbers, maximize the left argument and minimize the right argument.

• If multiplying two numbers, try the following:

• Maximize both arguments. This gives us the maximal result when multiplying two positive numbers.

• Minimize both arguments. This gives us the maximal result when multiplying two negative numbers, since a negative times a negative equals a positive.

• Minimize the left argument and maximize the right argument, or vice versa. We'd rather multiply two positives or two negatives and get a positive result, but if we have to multiply a positive and a negative and get a negative result, we want it to be as close to zero as possible. To do so, we minimize the positive number and maximize the negative number.

• This is a very clever optimization, I like it. Aug 28, 2011 at 5:44