Creating an expression with a maximum value

Question

Given n integers, is there an O(n) or O(n log n) algorithm that can calculate the maximum value of a mathematical expression that can be obtained by inserting the operators - , + , * and brackets between given numbers? Suppose only binary versions of the operators, therefore, not the unary minus, except in front of the first element, if necessary.

For example, given -3 -4 5 , we can construct the expression (-3) * (-4) * 5 , the value of which is 60 and the maximum possible.

Background:

I came across this problem some time ago, studying genetic algorithms, and found out that it can be solved quite simply using the classical genetic algorithm. However, this is slow, and it's just theoretical, since in practice the code gets pretty ugly (evaluate the expression, check the placement of the brackets, etc.). Moreover, we are not guaranteed to find the absolute maximum.

All of these shortcomings of genetic algorithms made me wonder: since we don’t need to worry about separation, is there a way to do this efficiently with a more classical approach like dynamic programming or a greedy strategy?

Update:

Here's the F # program that implements the DP solution proposed by @Keith Randall, along with my improvement, which I wrote in a comment on his post. This is very inefficient, but I maintain that it is polynomial and has cubic complexity. It starts in a few seconds for ~ 50 element arrays. It would probably be faster if it were written entirely imperatively, since a lot of the time was probably wasted on collecting and transitions.

 open System open System.IO open System.Collections.Generic let Solve (arr : int array) = let memo = new Dictionary<int * int * int, int>() 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 -> 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 ij) * (Inner (i + 1) dr k) ] |> List.max) memo.Item(st, dr, last) | 1 -> 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 ij) + (Inner (i + 1) dr k) ] |> List.max) memo.Item(st, dr, last) | 2 -> 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 ij) - (Inner (i + 1) dr k) ] |> List.max) memo.Item(st, dr, last) let noFirst = [ for i in 0 .. 2 do yield Inner 0 (arr.Length - 1) i ] |> List.max arr.[0] <- -1 * arr.[0] memo.Clear() let yesFirst = [ for i in 0 .. 2 do yield Inner 0 (arr.Length - 1) i ] |> List.max [noFirst; yesFirst] |> List.max let _ = printfn "%d" <| Solve [|-10; 10; -10|] printfn "%d" <| Solve [|2; -2; -1|] printfn "%d" <| Solve [|-5; -3; -2; 0; 1; -1; -1; 6|] printfn "%d" <| 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;|] 

Results:

1000
6
540
2147376354

The latter is most likely an overflow error, I'm just trying to show that a relatively large test runs too fast for it to be exponential.

Answer 1

The proposed solution is proposed here:

 def max_result(a_): memo = {} a = list(a_) a.insert(0, 0) return min_and_max(a, 0, len(a)-1, memo)[1] def min_and_max(a, i, j, memo): if (i, j) in memo: return memo[i, j] if i == j: return (a[i], a[i]) min_val = max_val = None for k in range(i, j): left = min_and_max(a, i, k, memo) right = min_and_max(a, k+1, j, memo) for op in "*-+": for x in left: for y in right: val = apply(x, y, op) if min_val == None or val < min_val: min_val = val if max_val == None or val > max_val: max_val = val ret = (min_val, max_val) memo[i, j] = ret return ret def apply(x, y, op): if op == '*': return x*y if op == '+': return x+y return xy 

max_result is the main function, and min_and_max is the helper. The latter returns the minimum and maximum results that can be achieved using the subsequence a [i..j].

It is assumed that the maximum and minimum results of the sequences are composed of the maximum and minimum results of the subsequences. Under this assumption, the problem has an optimal substructure and can be solved using dynamic programming (or memoization). Operating time O (n ^ 3).

I did not prove the correctness, but I checked its conclusion against a brute force solution with thousands of small random generated inputs.

It handles the possibility of getting the unary minus by inserting zero at the beginning of the sequence.

EDIT

I thought a little more about this problem, and I believe that it can be reduced to a simpler problem, in which all values ​​are (strictly) positive, and only the * and + operators are allowed.

Just remove all zeros from the sequence and replace the negative numbers with their absolute value.

In addition, if there is not one in the resulting sequence, the result will be just the product of all numbers.

After this reduction, a simple dynamic programming algorithm will work.

EDIT 2

Based on previous views, I think I found a linear solution:

 def reduce(a): return filter(lambda x: x > 0, map(abs, a)) def max_result(a): b = reduce(a) if len(b) == 0: return 0 return max_result_aux(b) def max_result_aux(b): best = [1] * (len(b) + 1) for i in range(len(b)): j = i sum = 0 while j >= 0 and ij <= 2: sum += b[j] best[i+1] = max(best[i+1], best[j] * sum) j -= 1 return best[len(b)] 

best [i] - the maximum result that can be achieved by the subsequence b [0 .. (i-1)].

EDIT 3

Here is an argument in favor of the O(n) algorithm, based on the following assumption:

You can always achieve maximum results with an expression of the form

+/- (a_1 +/- ... +/- a_i) * ... * (a_j +/- ... +/- a_n)

That is: a product of factors consisting of an algebraic sum of terms (including the case of only one factor).

I will also use the following lemmas, which are easy to prove:

Lemma 1: x*y >= x+y for all x,y such that x,y >= 2

Lemma 2: abs(x_1) + ... + abs(x_n) >= abs(x_1 +/- ... +/- x_n)

Here it is.

The sign of each factor does not matter, because you can always make a product positive using the leading unary minus. Therefore, to maximize the product, we need to maximize the absolute value of each factor.

Leaving aside the trivial case when all numbers are zeros, in the optimal solution, not a single factor will consist only of zeros. Therefore, since zeros do not affect every sum of members, and each factor will have at least one nonzero number, we can remove all zeros. From now on, suppose that there are no zeros.

Let the concentration in each amount be expressed separately:

(x_1 +/- x_2 +/- ... +/- x_n)

By virtue of Lemma 2, the maximum absolute value that each factor can obtain is the sum of the absolute values ​​of each term. This can be achieved as follows:

If x_1 is positive, add all the positive members and subtract all the negative members. If x_1 is negative, subtract all the positive members and add all the negative members.

This means that the sign of each term does not matter, we can consider the absolute value of each number and use only the operator + internal factors. From now on, let all numbers be positive.

The most important step that leads to the O(n) algorithm is the proof that the maximum result can always be achieved with factors that have no more than three members.

Suppose that we have a coefficient of more than three members, by Lemma 1 we can divide it into two smaller factors of 2 or more members each (therefore, each of them can contain up to 2 or more) without reducing the overall result. We can break it down several times until factors remain in more than 3 terms.

This completes the argument. I still have not found a full justification for the initial assumption. But I checked my code with millions of randomly generated cases and couldn't break it.

Answer 2

In O (N) one can find reasonably large value. Consider this greedy algorithm.

• Find all positive numbers ≥ 2. Save the result as A.
• Count all the "-1". Save the result as B.
• Find all negative numbers ≤ -2. Save the result as C.
• Count all the "1". Save the result as D.
• Initialize the product to 1.
• If A is not empty, multiply Product by product A.
• If C is not empty and even has a counter, multiply Product by the product of C.
• If C has an odd number, take the smallest number from C (save it as x) and multiply Product by the product of the rest of C.
• If x is set and B is nonzero, compare Product & times; -x with product & minus; x + 1.
  • If the first is strictly larger, reduce B by 1 and multiply Product by -x, then remove x.
  • If the latter is more, do nothing.
• Set the result to 0. If Product ≠ 1, add it to Result.
• Add D to the result, representing the addition of D "1" s.
• Add B to the result, representing the subtraction of B "-1" s.
• If x is given, print x from the result.

Temporary difficulties:

1. O (N), 2. O (N), 3. O (N), 4. O (N), 5. O (1), 6. O (N), 7. O (N), 8 .O (N), 9. O (1), 10. O (1), 11. O (1), 12. O (1), 13. O (1),

therefore, the whole algorithm works in O (N) time.

---

Session Example:

 -3 -4 5 

• A = [5]
• B = 0
• C = [-3, -4]
• D = 1
• Product = 1
• A is not empty, therefore Product = 5.
• C is even, so Product = 5 × -3 times; -4 = 60
• -
• -
• Product ≠ 1, therefore Result = 60.
• -
• -
• -

5 times -3 times; -4 = 60

 -5 -3 -2 0 1 -1 -1 6 

• A = [6]
• B = 2
• C = [-5, -3, -2]
• D = 1
• Product = 1
• A is not empty, therefore Product = 6
• -
• C is odd, so x = -2, and Product = 6 × -5 times; -3 = 90.
• x is given and B is nonzero. Compare product and time; -x = 180 and Product & minus; x + 1 = 93. Since the first is bigger, we reset B to 1, Product to 180 and delete x.
• Result = 180.
• Result = 180 + 1 = 181
• Result = 181 + 1 = 182
• -

6 times -5 times; -3 times; -2 times; -1 + 1 ± (-1) + 0 = 182

 2 -2 -1 

• A = [2]
• B = 1
• C = [-2]
• D = 0
• Product = 1
• Product = 2
• -
• x = -2, The product does not change.
• B is nonzero. Compare product and time; -x = 4 and Product & minus; x + 1 = 5. Since the latter is greater, we do nothing.
• Result = 2
• -
• Result = 2 + 1 = 3
• Result = 3 & minus; (-2) = 5.

2 & minus; (-1) & minus; (-2) = 5.

Answer 3

You should be able to do this with dynamic programming. Let x_i be your input numbers. Then let M(a,b) be the maximum value that you can get with the subsequence x_a through x_b . Then you can calculate:

 M(a,a) = x_a M(a,b) = max_i(max(M(a,i)*M(i+1,b), M(a,i)+M(i+1,b), M(a,i)-M(i+1,b)) 

edit:

I think you need to calculate both the maximum and the minimum computable value using each subsequence. So

 Max(a,a) = Min(a,a) = x_a Max(a,b) = max_i(max(Max(a,i)*Max(i+1,b), Max(a,i)*Min(i+1,b), Min(a,i)*Max(i+1,b), Min(a,i)*Min(i+1,b), Max(a,i)+Max(i+1,b), Max(a,i)-Min(i+1,b)) ...similarly for Min(a,b)... 

Answer 4

Work in reverse polish - this way you don't have to deal with parentheses. Then put in front of each number (thus making it positive). Finally, multiply them all together. Not sure about the difficulty, perhaps around O(N) .

EDIT: forgot about 0. If this happens in your input set, add it to the result.

Answer 5

This feels NP Complete for me, although I haven't figured out how to make the cut yet. If I'm right, then I could say

• No one in the world knows if there is any polynomial algorithm, not to mention O(n log n) , but most computer scientists suspect not.
• To evaluate the response, there are poly time algorithms, such as the genetic algorithm you describe.
• Actually, I think the question you want to ask is "Is there a useful O(n) or O(n log n) algorithm for estimating the maximum value?"

Answer 6

This is my first post on stackoverflow, so I apologize in advance for the lack of any prior etiquette. In addition, in the interest of full disclosure, Dave brought this issue to my attention.

Here's an O(N^2logN) solution, mainly because of the repeated sorting step in the for loop.

• Absolute values: Removing zero elements and sorting by absolute value. Since you are allowed to put a negative sign in front of your final result, it does not matter if your answer is negative or positive. Only the absolute values ​​of all numbers in a given matter.

• Multiplication only by numbers> 1: Let us observe that for any set of positive integers greater than 1 (for example, {2,3,4} ), the greatest result is obtained from multiplication. This can be shown by an enumeration technique or an argument of contradiction over the allowed operations + and -. e.g. (2+3)*4 = 2*4 + 3*4 < 3*4 + 3*4 = 2*(3*4) . In other words, multiplication is the most “powerful” operation (with the exception of 1s).

• Adding 1s to the smallest non-1 numbers: For 1s, since multiplication is a futile operation, we better add. Here again, the complete ordering of the addition result is shown. For rhetoric, again consider the set {2,3,4} . Note that: 2*3*(4+1) <= 2*(3+1)*4 <= (2+1)*3*4 . In other words, we get the largest “mileage” out of 1, adding it to the smallest existing non-1 element in the set. Given a sorted set, this can be done in O(N^2logN) .

Here is what the pseudo code looks like:

 S = input set of integers; S.absolute(); S.sort(); //delete all the 0 elements S.removeZeros(); //remove all 1 elements from the sorted list, and store them ones = S.removeOnes(); //now S contains only integers > 1, in ascending order S[0] ... S[end] for each 1 in ones: S[0] = S[0] + 1; S.sort(); end max_result = Product(S); 

Answer 7

I know I'm late for the party, but I took it as a challenge to myself. Here is the solution I came up with.

 type Operation = | Add | Sub | Mult type 'a Expr = | Op of 'a Expr * Operation * 'a Expr | Value of 'a let rec eval = function | Op (a, Add, b) -> (eval a) + (eval b) | Op (a, Sub, b) -> (eval a) - (eval b) | Op (a, Mult, b) -> (eval a) * (eval b) | Value x -> x let rec toString : int Expr -> string = function | Op (a, Add, b) -> (toString a) + " + " + (toString b) | Op (a, Sub, b) -> (toString a) + " - " + (toString b) | Op (a, Mult, b) -> (toString a) + " * " + (toString b) | Value x -> string x let appendExpr (a:'a Expr) (o:Operation) (v:'a) = match o, a with | Mult, Op(x, o2, y) -> Op(x, o2, Op(y, o, Value v)) | _ -> Op(a, o, Value v) let genExprs (xs:'a list) : 'a Expr seq = let rec permute xs e = match xs with | x::xs -> [Add; Sub; Mult] |> Seq.map (fun o -> appendExpr eox) |> Seq.map (permute xs) |> Seq.concat | [] -> seq [e] match xs with | x::xs -> permute xs (Value x) | [] -> Seq.empty let findBest xs = let best,result = genExprs xs |> Seq.map (fun e -> e,eval e) |> Seq.maxBy snd toString best + " = " + string result 

findBest [-3; -4; 5]
returns "-3 * -4 * 5 = 60"

findBest [0; 10; -4; 0; 52; -2; -40]
returns "0 - 10 * -4 + 0 + 52 * -2 * -40 = 4200"

It should work with any type-compatible mapping and basic math operators, but FSI will limit it to ints.