Find the maximum operation

Question

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.

Answer 1

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.

Answer 2

Haskell, 126 characters

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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]

Answer 7

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