建立具有最大值的表达式

Question

给定n整数，是有一个O(n)或O(n log n)能够计算可通过将操作员获得的数学表达式的最大值算法-，+，*和给定的数字之间括号？仅假定运算符的二进制变体，因此不取一元减，除非需要，请在第一个元素之前。

例如，给定-3 -4 5，我们可以构建表达式(-3) * (-4) * 5，其值为60，并且可能的最大值。

背景：

前一段时间，我在研究遗传算法时偶然发现了这个问题，并了解到可以使用经典遗传算法非常简单地解决它。但是，它运行缓慢，并且理论上只是简单的，因为代码在实践中变得很丑陋（评估表达式，检查方括号的正确放置等）。此外，我们也不保证找到绝对最大值。

遗传算法的所有这些缺点让我感到纳闷：既然我们不必担心除法问题，是否有办法以更经典的方法（例如动态编程或贪婪策略）有效地做到这一点？

更新：

这是一个F＃程序，它实现了@Keith Randall提出的DP解决方案以及我的改进，我在对他的帖子的评论中写道。这是非常低效的，但是我坚持认为它是多项式并且具有三次复杂性。它可以在几秒钟内运行约50个元素数组。如果以完全命令式的方式编写，可能会更快，因为可能会浪费大量时间来构建和遍历列表。

open System
open System.IO
open System.Collections.Generic

let Solve (arr : int array) =
    let memo = new Dictionary<int * int * int, int>()

    let rec Inner st dr last = 
        if st = dr then 
            arr.[st]
        else
            if memo.ContainsKey(st, dr, last) then
                memo.Item(st, dr, last)
            else
                match last with
                | 0 ->  memo.Add((st, dr, last),
                            [
                                for i in [st .. dr - 1] do
                                    for j in 0 .. 2 do
                                        for k in 0 .. 2 do
                                            yield (Inner st i j) * (Inner (i + 1) dr k)
                            ] |> List.max) 
                        memo.Item(st, dr, last)

                | 1 ->  memo.Add((st, dr, last),
                            [
                                for i in [st .. dr - 1] do
                                    for j in 0 .. 2 do
                                        for k in 0 .. 2 do
                                            yield (Inner st i j) + (Inner (i + 1) dr k)
                            ] |> List.max) 
                        memo.Item(st, dr, last)

                | 2 ->  memo.Add((st, dr, last),
                            [
                                for i in [st .. dr - 1] do
                                    for j in 0 .. 2 do
                                        for k in 0 .. 2 do
                                            yield (Inner st i j) - (Inner (i + 1) dr k)
                            ] |> List.max) 
                        memo.Item(st, dr, last)

    let noFirst = [ for i in 0 .. 2 do yield Inner 0 (arr.Length - 1) i ] |> List.max

    arr.[0] <- -1 * arr.[0]
    memo.Clear()
    let yesFirst = [ for i in 0 .. 2 do yield Inner 0 (arr.Length - 1) i ] |> List.max

    [noFirst; yesFirst] |> List.max

let _ = 
    printfn "%d" <| Solve [|-10; 10; -10|]
    printfn "%d" <| Solve [|2; -2; -1|]
    printfn "%d" <| Solve [|-5; -3; -2; 0; 1; -1; -1; 6|]
    printfn "%d" <| Solve [|-5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6;|]

结果：

1000
6
540
2147376354

最后一个很可能是由于溢出而导致的错误，我只是想表明一个相对较大的测试运行得太快而无法指数化。

Answer 1

这是一个建议的解决方案：

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

我还没有证明其正确性，但我已经针对具有数千个随机生成的小输入的蛮力解决方案验证了它的输出。

它通过在序列的开头插入零来处理前导一元减号的可能性。

编辑

一直在思考这个问题，我相信它可以简化为一个更简单的问题，其中所有值（严格）都是正数，并且只允许运算符 * 和 +。

只需从序列中删除所有零并用它们的绝对值替换负数。

此外，如果结果序列中没有数字，则结果只是所有数字的乘积。

在这种减少之后，简单的动态规划算法就可以工作了。

编辑 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 或更多），而不会减少总结果。我们可以反复分解它，直到不剩下超过 3 项的因子。

至此，论证完毕。我仍然没有找到最初假设的完整理由。但是我用数百万个随机生成的案例测试了我的代码并且无法破解它。