# Find the maximum operation

The challenge is to find the maximum number you can get from a list of integer using basic arithmetic operators (addition, substraction, multiplication, unary negation)

Input

A list of integers

Output

The maximum result using every integer in the intput.

The input order doesn't matter, result should be the same.

You do not need to output the full operation, just the result.

Examples

Input : 3 0 1
Output : 4 (3 + 1 + 0)

Input : 3 1 1 2 2
Output : 27 ((2+1)*(2+1)*3))

Input : -1 5 0 6
Output : 36 (6 * (5 - (-1)) +0)

Input : -10 -10 -10
Output : 1000 -((-10) * (-10) * (-10))

Input : 1 1 1 1 1
Output : 6 ((1+1+1)*(1+1))


Rules

• Shortest code wins

• Standard "loopholes" apply

• You may only use + * - operators (addition, multiplication, substraction, unary negation)

• The code should work as long as the result can be stored on a 32 bit Integer.

• Any overflow behaviour is up to you.

I hope this is clear enough, this is my first Code Golf challenge suggestion.

• One of your examples is using an operation which isn't permitted: if unary negation is intended to be in your whitelist then subtraction isn't really necessary. – Peter Taylor Aug 29 '14 at 10:21
• Editted and added unary negation. Substraction is kept in the whitelist. – CNicolas Aug 29 '14 at 10:28
• Does it have to be a full program or is a function enough? – ThreeFx Aug 29 '14 at 11:52
• Full program. Even better if it can be run online, but obviously not mandatory – CNicolas Aug 29 '14 at 12:28
• @INSeed Should i add a way to run online? – proud haskeller Aug 30 '14 at 19:21

# C - 224 bytes - Running time O(n)

o=0,w=0,n[55],t,*m=n,*p=n;main(r){for(;scanf("%d",++p);t<3?--p,w+=t/2,o+=t&1:t<*m|m==n?m=p:9)t=*p=abs(*p);t=o<w?o:w;o-=t;w-=t;t+=o/3;for(o%3?o%3-2?t?t--,w+=2:++*m:w++:9;t--;)r*=3;for(r<<=w;--p>n;)r*=*p;printf("%d",r>1?r:o);}


It was amusing to see only exponential-time solutions for a linear-time problem, but I suppose it was the logical way to proceed since there were no bonus points for actually having an algorithm, which is an anagram of logarithm.

After converting negative numbers to positive and discarding zeroes, clearly we are mostly interested in multiplication. We want to maximize the logarithm of the final number.

log(a + b) < log(a) + log(b) except when a = 1 or b = 1, so ones are the only case in which we are interested in adding anything together. In general it is better to add a 1 to a smaller number, because that causes a bigger increase in logarithm, i.e. a larger percentage increase, than adding 1 to a big number. There are four possible scenarios, ordered most to least preferable, for utilizing ones:

1. Adding one to a 2 gives +log .405 [log(3) - log(2)]
2. Combining ones into threes gives +log .366 per one [log(3) / 3]
3. Making a 2 out of ones gives +log .347 per one [log(2) / 2]
4. Adding one to a number 3 or higher gives +log .288 or less [log(4) - log(3)]

The program keeps track of the number of ones, the number of twos, and the minimum number greater than 2, and goes down the list of the most to least preferable ways of using the ones. Finally, it multiplies all the remaining numbers.

this is just brute-forcing, with the exception of ignoring the sign of the input and ignoring subtraction and unary negation.

import Data.List
f[x]=abs x::Int
f l=maximum$subsequences l\\[[],l]>>= \p->[f p+f(l\\p),f p*f(l\\p)] main=interact$show.f.read


this code is extremely slow. the code recursively calculates f on each subsequence of the input four times (except for [] and the input itself). but hey, it's code golf.

# SWI-Prolog - 250

Oh boy, I spent way too long on this.

o(A,B,A+B).
o(A,B,A-B).
o(A,B,A*B).
t([],0).
t([A,B|T],D):-t(T,Q),o(A,B,C),o(C,Q,D).
t([A|T],C):-t(T,Q),o(A,Q,C).
a(A):-t(A,B),n(C),B>C,retract(n(C)),assert(n(B)).
m(A):-assert(n(0)),\+p(A),n(R),R2 is R,write(R2).
p(A):-permutation([0|A],B),a(B),0=1.


Called from command line (e.g.):

> swipl -s filename.pl -g "m([1, 1, 1, 1, 1])" -t halt
6


(For no particlar reason, I found it awesome that my golfed function names spell "tomato pot.")

Ungolfed version:

% Possible operations
operation(Left, Right, Left + Right).
operation(Left, Right, Left - Right).
operation(Left, Right, Left * Right).

% Possible ways to transform
transform([], 0).
transform([A, B|T], D) :- transform(T, Q), operation(A, B, C), operation(C, Q, D).
transform([A|T], C) :- transform(T, Q), operation(A, Q, C).

% Throw the given array through every possible transformation and update the max
all_transforms(A) :- transform(A, B), n(C), B>C, retract(n(C)), assert(n(B)).

% Find all the permutations and transformations, then fail and continue execution.
prog(A) :- assert(n(0)), !, permutation([0|A], B), all_transforms(B), fail.

% End the program
finished :- n(R), write(R), nl, R2 is R, write(R2), nl.

% Run the program
main(A) :- ignore(prog(A)), finished.


Explanation:

1. Take in an array as an argument.
2. Get all permutations of the array.
3. Find some arrangement of operators to add to the array. (This is done via dynamic programming, seeing whether it's better if we combine the first two elements or not.)
4. Check this against our current max value. If it's better, replace it.
5. Tell the program we failed so that it keeps checking, but then negate that (using ignore or \+) to let the predicate overall return true and continue.
6. We're given a string of predicates, instead of a number, so assign it using is and then write it.

# Scala, 134

print(args.map(Math abs _.toInt)./:(Seq(Array(0)))((l,a)=>l.map(a+:_)++l.flatMap(_.permutations.map{r=>r(0)+=a;r}))map(_.product)max)


Ungolfed & commented:

print(
args
.map(Math abs _.toInt)                     // to int, ignoring -
.foldLeft(Seq(Array(0))){ (list,num) =>    // build up a list of sums of numbers
list.map(num+:_) ++                      // either add the new number to the list
list.flatMap(_.permutations.map{ copy =>
copy(0)+=num                           // or add it to one of the elements
copy
})
}
.map(_.product) // take the maximum of the the products-of-sums
.max
)


A slightly different approach, from realizing that the biggest answer can always be expressed as a product of sums.

So close, but a bunch of library stupidity (permutations returns an Iterator instead of a Seq, horrible type inference on empty sequences, Array.update returning Unit) did me in.

## Python 278 (O(n!))

from itertools import*
def f(n):
f,n,m=lambda n:[(n,)]+[(x,)+y for x in range(1,n)for y in f(n-x)],map(abs,map(int,n.split())),0
for p,j in product(permutations(n),f(len(n))):
i=iter(p)
m=max(m,reduce(lambda e,p:e*p,(sum(zip(*zip([0]*e,i))[1])for e in j)))
return m


## Explanation

1. Unary Negate should be judiciously used to convert all negative numbers to positive
2. Find all possible permutations of the numbers
3. Using Integer partition to find all power-sets of a given permutation
4. Find the product of the sums
5. Return the maximum of the product of the sums

# Haskell - 295 290 265 246 203 189 182 bytes

Finally works! Also now it is a brute force rather than a dynamic solution.

Thanks to proudhaskeller for some of the golfing tips.

This is probably not a fully golfed solution because I actually suck at golfing, but it is the best I can come up with (and it looks complicated, so I got that going for me):

import Data.List
main=interact$show.g.read g x=maximum[product$a#b|a<-sequence$replicate(length x-1)[0,1],b<-permutations x] (a:b)#(c:d:e)|a>0=b#(c+d:e)|0<1=c:b#(d:e) _#x=x  New test cases: [1,1,1,2,2] 12 [1,1,3,3,3] 54 [1,1,1,1,1,1,1,1,5,3] 270  Solution explanation: The main function just gets an input and runs g with it. g takes the input and returns the maximum of all possible combinations of sums and list orders. # is the function which calculates the sums in a list like this: a = [1,0,0,1] b = [1,1,1,2,2] a#b = [2,1,4]  • this seems like quite a performance-driven solution. – proud haskeller Aug 29 '14 at 16:01 • can you please write newlines instead of ; when possible? it doesn't change the byte count but helps the readability troumendously – proud haskeller Aug 29 '14 at 16:31 • @proudhaskeller I had no idea how to brute force this so I had to come up with something else :D – ThreeFx Aug 29 '14 at 17:13 • my advice for golfing this - 1) inline every function that is used just once (unless it uses pattern matching or guards). 2) you can implement d as d n=[0,2,1]!!n or d n=mod(3-n)3. 3) make o and g take the length of the list instead of taking the list itself, as they only depend on the length (obviously this stands only as long as they aren't inlined). 4) replace otherwise with 0<1. 5) make the last definition of r be r$o x:y. 6) remove the a@ and replace a with x:y. good luck with your golfing! – proud haskeller Aug 29 '14 at 18:48
• Your algorithm gives the wrong answer for [3,3,3,2,2,2,1,1,1]. I ran your code, and it returns 216 (the largest result I was able to come up with was 729). – Brilliand Aug 29 '14 at 20:56

## GolfScript (52 chars)

~]0-{abs}%.1-.1,or@,@,-,-1%{!\\$.0=3<@+{()}1if+}/{*}*


Online demo

feersum's analysis is pretty good but it can be taken further if the goal is golfing rather than efficiency. In pseudo-code:

filter zeros from input and replace negatives with their absolute value
filter ones to get A[]
count the ones removed to get C
while (C > 0) {
sort A
if (A[0] < 3 || C == 1) A[0]++
else A.append(1)
C--
}
fold a multiply over A