Вот предлагаемое решение:
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 x-y
max_result является основной функцией, а min_and_max является вспомогательной. Последний возвращает минимальные и максимальные результаты, которые могут быть достигнуты с помощью подпоследовательности a [i..j].
Предполагается, что максимальный и минимальный результаты последовательностей составлены из максимальных и минимальных результатов подпоследовательностей. В этом предположении проблема имеет оптимальную подструктуру и может быть решена с помощью динамического программирования (или запоминания). Время выполнения O (n ^ 3).
Я не доказал правильность, но я проверил его результаты по решению грубой силы с тысячами небольших случайно сгенерированных входных данных.
Он обрабатывает возможность начального унарного минуса, вставляя ноль в начале последовательности.
EDIT
Я немного больше думал об этой проблеме, и я считаю, что ее можно свести к более простой задаче, в которой все значения (строго) положительны и допускаются только операторы * и +.
Просто удалите все нули из последовательности и замените отрицательные числа их абсолютными значениями.
Кроме того, если в результирующей последовательности нет ни одного, результатом будет просто произведение всех чисел.
После этого сокращения будет работать простой алгоритм динамического программирования.
РЕДАКТИРОВАТЬ 2
Основываясь на предыдущих выводах, я думаю, что нашел линейное решение:
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 i-j <= 2:
sum += b[j]
best[i+1] = max(best[i+1], best[j] * sum)
j -= 1
return best[len(b)]
best [i] - это максимальный результат, который может быть достигнут с помощью подпоследовательности b [0 .. (i-1)].
РЕДАКТИРОВАТЬ 3
Вот аргумент в пользу алгоритма O(n), основанный на следующем предположении:
Вы всегда можете достичь максимального результата с помощью выражения вида
+/- (a_1 +/- ... +/- a_i) * ... * (a_j +/- ... +/- a_n)
То есть: произведение факторов, составленное из алгебраической суммы членов (включая случай только одного фактора).
Я также буду использовать следующие леммы, которые легко доказать:
Лемма 1: x*y >= x+y для всех x,y такая, что x,y >= 2
Лемма 2: abs(x_1) + ... + abs(x_n) >= abs(x_1 +/- ... +/- x_n)
Вот так.
Знак каждого фактора не имеет значения, поскольку вы всегда можете сделать продукт положительным, используя ведущий унарный минус. Следовательно, чтобы максимизировать продукт, нам нужно максимизировать абсолютное значение каждого фактора.
Если оставить в стороне тривиальный случай, когда все числа являются нулями, в оптимальном решении ни один фактор не будет состоять только из нулей. Следовательно, поскольку нули не влияют на каждую сумму слагаемых, и каждый фактор будет иметь хотя бы одно ненулевое число, мы можем удалить все нули. Теперь предположим, что нулей нет.
Давайте сконцентрируемся в каждой сумме условий отдельно:
(x_1 +/- x_2 +/- ... +/- x_n)
По Лемма 2 максимальное абсолютное значение, которое может получить каждый фактор, является суммой абсолютных значений каждого члена. Это может быть достигнуто следующим образом:
Если x_1 положительный, добавьте все положительные и вычтите все отрицательные. Если x_1 отрицательный, вычтите все положительные члены и добавьте все отрицательные.
Это означает, что знак каждого члена не имеет значения, мы можем рассмотреть абсолютное значение каждого числа и использовать только оператор + внутри факторов. Теперь давайте рассмотрим все числа положительные.
Важнейший шаг, который приводит к алгоритму O(n), состоит в том, чтобы доказать, что максимальный результат всегда может быть достигнут с факторами, которые имеют не более 3 членов.
Предположим, что у нас есть коэффициент более 3-х терминов, по Лемма 1 мы можем разбить его на два меньших фактора по 2 или более слагаемых каждый (следовательно, каждый добавляет до 2 или более), без уменьшение общего результата. Мы можем неоднократно разбивать его до тех пор, пока не останется больше трех членов.
Это завершает аргумент. Я до сих пор не нашел полного обоснования первоначального предположения. Но я протестировал свой код с миллионами случайно сгенерированных случаев и не смог его сломать.