3
\$\begingroup\$

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?

\$\endgroup\$
7
  • 2
    \$\begingroup\$ You could use dynamic programming to get some improvement. But does this belong here or on StackOverflow? \$\endgroup\$ Aug 26, 2011 at 11:43
  • 2
    \$\begingroup\$ I'd say it belongs here as it's a programming puzzle. \$\endgroup\$ Aug 26, 2011 at 14:28
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Gareth
    Aug 26, 2011 at 14:47
  • \$\begingroup\$ Your example is bad. After performing the addition (1st step), you should have 5 * 5 + 5 * -2. \$\endgroup\$ Aug 26, 2011 at 19:16
  • \$\begingroup\$ @trinithis: I think Clueless had in mind 5 * 5 - (3 + 8) * -2 for the first addition step. \$\endgroup\$
    – Briguy37
    Aug 26, 2011 at 19:32

1 Answer 1

5
\$\begingroup\$

Haskell, O(n3)

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.

\$\endgroup\$
1
  • \$\begingroup\$ This is a very clever optimization, I like it. \$\endgroup\$
    – Clueless
    Aug 28, 2011 at 5:44

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