O desafio é encontrar o número máximo que você pode obter de uma lista de números inteiros usando operadores aritméticos básicos (adição, subtração, multiplicação, negação unária)

Entrada

Uma lista de números inteiros

Resultado

O resultado máximo usando todos os números inteiros na entrada.

A ordem de entrada não importa, o resultado deve ser o mesmo.

Você não precisa produzir a operação completa, apenas o resultado.

Exemplos

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))

Regras

• O código mais curto vence

• Aplicam-se "brechas" padrão

• Você pode usar apenas operadores + * (adição, multiplicação, subtração, negação unária)

• O código deve funcionar desde que o resultado possa ser armazenado em um número inteiro de 32 bits.

• Qualquer comportamento de estouro depende de você.

Espero que isso esteja claro o suficiente, esta é minha primeira sugestão de desafio do Code Golf.

C - 224 bytes - Tempo de execução 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);}

Foi divertido ver apenas soluções de tempo exponencial para um problema de tempo linear, mas suponho que era a maneira lógica de prosseguir, pois não havia pontos de bônus por realmente ter um algoritmo, que é um anagrama de logaritmo.

Depois de converter números negativos em positivos e descartar zeros, claramente estamos interessados ​​principalmente na multiplicação. Queremos maximizar o logaritmo do número final.

log (a + b) <log (a) + log (b), exceto quando a = 1 ou b = 1, então esse é o único caso em que estamos interessados ​​em adicionar algo. Em geral, é melhor adicionar 1 a um número menor, porque isso causa um aumento maior no logaritmo, ou seja, um aumento percentual maior do que adicionar 1 a um número grande. Existem quatro cenários possíveis, ordenados do mais ao menos preferível, para utilização dos seguintes:

1. Adicionar um a 2 dá + log .405 [log (3) - log (2)]
2. A combinação de três em três dá + log .366 por um [log (3) / 3]
3. Fazer 2 de um dá + log 0,347 por um [log (2) / 2]
4. Adicionar um a um número 3 ou superior fornece + log .288 ou menos [log (4) - log (3)]

O programa monitora o número de unidades, o número de dois e o número mínimo maior que 2 e desce a lista das maneiras mais ou menos preferíveis de usá-las. Por fim, multiplica todos os números restantes.

Haskell, 126 caracteres

isso é apenas uma força bruta, com exceção de ignorar o sinal da entrada e de subtração e negação unária.

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

esse código é extremamente lento. o código calcula recursivamente f em cada subsequência da entrada quatro vezes _{(exceto [] e a própria entrada)} . mas ei, é código de golfe.

SWI-Prolog - 250

Oh garoto, eu gastei muito tempo nisso.

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.

Chamado a partir da linha de comando (por exemplo):

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

(Por nenhuma razão específica, achei incrível que os nomes das minhas funções de golfe escrevessem "pote de tomate".)

Versão não destruída:

% 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.

Explicação:

1. Pegue uma matriz como argumento.
2. Obtenha todas as permutações da matriz.
3. Encontre algum arranjo de operadores para adicionar à matriz. (Isso é feito por meio de programação dinâmica, verificando se é melhor combinarmos os dois primeiros elementos ou não.)
4. Verifique isso em relação ao nosso valor máximo atual. Se estiver melhor, substitua-o.
5. Diga ao programa que falhámos para que ele continue verificando, mas negue (usando ignoreou \+) para permitir que o predicado retorne truee continue.
6. Recebemos uma sequência de predicados, em vez de um número; portanto, atribua-o usando ise depois escreva-o.

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 & comentou:

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
)

Uma abordagem um pouco diferente, ao perceber que a maior resposta sempre pode ser expressa como um produto de somas.

Tão perto, mas um monte de estupidez de biblioteca (permutações retorna um Iterator em vez de uma Seq, inferência de tipo horrível em sequências vazias, Array.update retornando Unit) me ajudou.

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

Explicação

1. O Unary Negate deve ser usado criteriosamente para converter todos os números negativos em positivos
2. Encontre todas as permutações possíveis dos números
3. Usando a partição Inteira para encontrar todos os conjuntos de potência de uma determinada permutação
4. Encontre o produto das somas
5. Devolver o máximo do produto das somas

Haskell - 295 290 265 246 203 189 182 bytes

Finalmente funciona! Agora também é uma força bruta e não uma solução dinâmica.

Agradecemos a proudhaskeller por algumas dicas de golfe.

Provavelmente, essa não é uma solução completa para o golfe, porque na verdade sou péssima no golfe, mas é a melhor solução possível (e parece complicada, por isso compreendi isso):

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

Novos casos de teste:

[1,1,1,2,2]
12

[1,1,3,3,3]
54

[1,1,1,1,1,1,1,1,5,3]
270

Explicação da solução:

A mainfunção apenas obtém uma entrada e é executada gcom ela.

g pega a entrada e retorna o máximo de todas as combinações possíveis de somas e ordens de lista.

# é a função que calcula as somas em uma lista como esta:

a = [1,0,0,1]
b = [1,1,1,2,2]
a#b = [2,1,4]

GolfScript (52 caracteres)

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

Demonstração online

A análise do feersum é muito boa, mas pode ser levada mais longe se o objetivo é jogar golfe em vez de eficiência. No pseudo-código:

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