Задача состоит в том, чтобы найти максимальное число, которое вы можете получить из списка целых чисел, используя основные арифметические операторы (сложение, вычитание, умножение, унарное отрицание)

вход

Список целых чисел

Выход

Максимальный результат при использовании каждого целого числа в intput.

Порядок ввода не имеет значения, результат должен быть таким же.

Вам не нужно выводить полную операцию, только результат.

Примеры

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

правила

• Самый короткий код выигрывает

• Стандартные "лазейки" применяются

• Вы можете использовать только операторы + * - (сложение, умножение, вычитание, унарное отрицание)

• Код должен работать до тех пор, пока результат может быть сохранен в 32-битном Integer.

• Любое поведение переполнения зависит от вас.

Надеюсь, это достаточно ясно, это мое первое предложение Code Golf.

C - 224 байта - время работы 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);}

Было забавно видеть только экспоненциально-временные решения для задачи с линейным временем, но я полагаю, что это был логичный способ продолжить, поскольку не было никаких бонусных баллов за фактическое наличие алгоритма, который является анаграммой логарифма.

Очевидно, что после преобразования отрицательных чисел в положительные и отбрасывания нулей нас больше всего интересует умножение. Мы хотим максимизировать логарифм окончательного числа.

log (a + b) <log (a) + log (b) за исключением случаев, когда a = 1 или b = 1, поэтому это единственный случай, когда мы заинтересованы в добавлении чего-либо вместе. Обычно лучше добавить 1 к меньшему числу, потому что это вызывает большее увеличение логарифма, то есть большее процентное увеличение, чем добавление 1 к большому числу. Существует четыре возможных сценария, упорядоченных от наиболее к наименее предпочтительным, для их использования:

1. Добавление одного к 2 дает + log .405 [log (3) - log (2)]
2. Объединение в тройки дает + log .366 за один [log (3) / 3]
3. Создание 2 из них дает + log .347 за один [log (2) / 2]
4. Добавление одного к числу 3 или выше дает + log .288 или меньше [log (4) - log (3)]

Программа отслеживает количество единиц, количество двойок и минимальное число больше 2, и идет вниз по списку наиболее или менее предпочтительных способов их использования. Наконец, он умножает все оставшиеся числа.

Хаскель, 126 символов

это просто грубое принуждение, за исключением игнорирования знака ввода и игнорирования вычитания и унарного отрицания.

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

этот код очень медленный код рекурсивно вычисляет f для каждой подпоследовательности ввода четыре раза _{(за исключением [] и самого ввода)} . но эй, это код гольф.

SWI-Пролог - 250

О, мальчик, я слишком долго на это потратил.

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.

Вызывается из командной строки (например):

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

(Без особой причины я нашел удивительным, что мои названия функций в гольфе пишут "томатный горшок".)

Безголовая версия:

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

Объяснение:

1. Возьмите в качестве аргумента массив.
2. Получить все перестановки массива.
3. Найдите расположение операторов для добавления в массив. (Это делается с помощью динамического программирования, чтобы понять, будет ли лучше объединить первые два элемента или нет.)
4. Сравните это с нашим текущим максимальным значением. Если лучше, замени его.
5. Скажите программе, что мы потерпели неудачу, чтобы она продолжала проверять, но затем отмените это (используя ignoreили \+), чтобы предикат в целом вернулся trueи продолжил.
6. Нам дана строка предикатов вместо числа, поэтому присвойте его, используя, isа затем запишите.

Скала, 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 и прокомментировал:

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
)

Немного другой подход, от понимания того, что самый большой ответ всегда можно выразить как произведение сумм.

Так близко, но куча глупостей библиотеки (перестановки возвращают Iterator вместо Seq, ужасный вывод типа для пустых последовательностей, Array.update, возвращающий Unit) заставила меня задуматься.

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

объяснение

1. Унарное отрицание должно быть разумно использовано для преобразования всех отрицательных чисел в положительные
2. Найти все возможные перестановки чисел
3. Использование целочисленного разбиения для нахождения всех наборов мощности данной перестановки
4. Найти произведение сумм
5. Вернуть максимум произведения сумм

Haskell - 295 290 265 246 203 189 182 байта

Наконец работает! Также теперь это грубая сила, а не динамическое решение.

Спасибо гордому скелеру за некоторые советы по игре в гольф.

Вероятно, это не полностью решение для игры в гольф, потому что я на самом деле отстой в игре в гольф, но это лучшее, что я могу придумать (и это выглядит сложным, поэтому я понял, что для меня):

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

Новые тестовые случаи:

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

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

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

Объяснение решения:

mainФункция просто получает входной сигнал и работает gс ним.

g принимает входные данные и возвращает максимум всех возможных комбинаций сумм и порядков списка.

# это функция, которая вычисляет суммы в списке следующим образом:

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

GolfScript (52 символа)

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

Онлайн демо

Анализ feersum довольно хорош, но его можно продолжить, если цель - игра в гольф, а не эффективность. В псевдокоде:

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