构建具有最大值的表达式

下面是一个建议的解决方案:

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

最大结果是主函数,最小值和最大值是辅助函数。后者返回子序列a[i..j]可以获得的最小和最大结果。

我还没有证明它的正确性,但是我已经用一个带有数千个小的随机生成的输入的暴力解决方案验证了它的输出。

编辑

我对这个问题考虑得更多了,我相信它可以简化为一个更简单的问题,所有的值(严格地)都是正的,只允许使用运算符*和+。

只需去掉序列中的所有零,并用它们的绝对值替换负数。

在这个简化之后,简单的动态规划算法就可以工作了。

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

我还将使用以下易于证明的引理:

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项的情况下,总是可以得到最大的结果。

引理1 我们可以将其分解为两个较小的因子,每个因子包含2个或多个项(因此,每个项加起来等于2个或多个项),而不减少总结果。我们可以反复分解,直到没有超过3项的因素。

这就完成了论证。我还没有找到一个完整的理由来证明最初的假设。但我用数百万个随机生成的案例测试了我的代码,却无法破解它。

在O(N)中可以找到一个合理的大值。这是一个贪婪的算法。

1. A .
2. 数一数所有“-1”。将结果存储为 B类 .
3. 找出所有负数-2。将结果存储为 C级 .
4. D级
5. 初始化 产品 到1。
6. A 产品 A .
7. C级 不是空的并且有偶数,乘法 产品 副产品 C级
8. 如果 是奇数,取数量级中的最小数 C级 十 ),然后相乘 产品 是其他人的产物
9. 如果 十 B类 具有 产品x+1 .
   • 如果前者严格地较大,则减小 乘1和乘 产品 十 ,然后删除 十 .
   • 如果后者更大,什么也不要做。
10. 结果 产品 结果 .
11. D级 到 结果 ,表示 D级 “1”秒。
12. 添加 到 ,表示 B类
13. 如果 已设置,减去 十 从 .

1O(N),2。O(N),3。O(N),4。O(N),5。O(1),6。O(N),7。O(N),8。O(N),9。O(1),10。O(1),11。O(1),12。O(1),13。O(1),

因此整个算法的运行时间为O(N)。

-3 -4 5

1. = [5]
3. C级 = [-3, -4]
4. = 1
5. 产品
6. A 不是空的,所以 产品
7. C级 是平的,所以 = 5 × -3 × -4 = 60
8. -
9. -
10. 产品 结果
12. -
13. -

-5 -3 -2 0 1 -1 -1 6 

1. = [6]
2. B类 = 2
3. C级
4. D级 = 1
6. 不是空的,所以 产品 = 6
7. -
8. C级 十 =-2,和 产品 = 6 × -5 × -3 = 90.
9. 已设置并 产品×-x 产品x+1 = 93. 因为前者更大,我们重新设置 B类 至180并移除 十 .
11. 结果 = 180 + 1 = 181
12. 结果 = 181 + 1 = 182
13. -

2 -2 -1

1. = [2]
2. B类 = 1
3. = [-2]
4. D级 = 0
5. = 1
6. = 2
7. -
8. = -2, 产品
9. B类 不是零。比较 产品×-x = 5. 因为后者更大,我们什么也不做。
10. = 2
12. 结果 = 2 + 1 = 3
13. = 3 (-2) = 5.

2 (-1) (-2) = 5.

您应该能够用动态编程来实现这一点。让 x_i 输入数字。那就让我 M(a,b) 是子序列的最大值 x_a 通过 x_b . 然后可以计算:

M(a,a) = x_a
M(a,b) = max_i(max(M(a,i)*M(i+1,b), M(a,i)+M(i+1,b), M(a,i)-M(i+1,b))

编辑:

我认为您需要使用每个子序列计算最大和最小可计算值。所以呢

Max(a,a) = Min(a,a) = x_a
Max(a,b) = max_i(max(Max(a,i)*Max(i+1,b),
                     Max(a,i)*Min(i+1,b),
                     Min(a,i)*Max(i+1,b),
                     Min(a,i)*Min(i+1,b),
                     Max(a,i)+Max(i+1,b),
                     Max(a,i)-Min(i+1,b))
...similarly for Min(a,b)...

用反波兰语处理这个问题-这样你就不用处理括号了。接下来在每个-ve数字前面加一个-e(从而使其为正)。最后把它们加起来。不确定复杂性,可能是 O(N) .

我觉得这是NP完全的,虽然我还没有弄清楚如何减少。如果我是对的,那么我可以说

• 世界上没有人知道是否存在多项式算法,更不用说 O(n log n)
• O(n) 或

这是我在stackoverflow上的第一篇帖子,因此我提前为错过任何初步礼仪道歉。此外,为了充分披露,戴夫提请我注意这个问题。

O(N^2logN) 解决方案,主要是因为for循环中重复的排序步骤。

1. 删除零元素并按绝对值排序。既然你被允许在你的最终结果前加上一个否定的符号,那么你的答案是否定的还是肯定的并不重要。只有集合中所有数字的绝对值才重要。

2. 仅适用于数字>1的乘法: 我们观察到,对于任何一组大于1的正整数。 {2,3,4} (2+3)*4 = 2*4 + 3*4 < 3*4 + 3*4 = 2*(3*4) . 换句话说,乘法是最“强大”的运算(除了1)。

3. 对于1,因为乘法是一个无用的运算,我们最好是加法。这里我们再次展示了加法结果的完全排序。为了修辞,再考虑一下布景 2*3*(4+1) <= 2*(3+1)*4 <= (2+1)*3*4 O(N^2日志) .

下面是伪代码的样子:

S = input set of integers;

S.absolute();
S.sort();

//delete all the 0 elements
S.removeZeros();

//remove all 1 elements from the sorted list, and store them
ones = S.removeOnes();

//now S contains only integers > 1, in ascending order S[0] ... S[end]
for each 1 in ones:
   S[0] = S[0] + 1; 
   S.sort();
end

max_result = Product(S);

type Operation =
    | Add
    | Sub
    | Mult

type 'a Expr =
    | Op of 'a Expr * Operation * 'a Expr
    | Value of 'a

let rec eval = function
    | Op (a, Add, b)  -> (eval a) + (eval b)
    | Op (a, Sub, b)  -> (eval a) - (eval b)
    | Op (a, Mult, b) -> (eval a) * (eval b)
    | Value x -> x

let rec toString : int Expr -> string = function
    | Op (a, Add, b)  -> (toString a) + " + " + (toString b)
    | Op (a, Sub, b)  -> (toString a) + " - " + (toString b)
    | Op (a, Mult, b) -> (toString a) + " * " + (toString b)
    | Value x -> string x

let appendExpr (a:'a Expr) (o:Operation) (v:'a) =
    match o, a with
    | Mult, Op(x, o2, y) -> Op(x, o2, Op(y, o, Value v))
    | _                  -> Op(a, o, Value v)

let genExprs (xs:'a list) : 'a Expr seq =
    let rec permute xs e =
        match xs with
        | x::xs ->
            [Add; Sub; Mult]
            |> Seq.map (fun o -> appendExpr e o x)
            |> Seq.map (permute xs)
            |> Seq.concat
        | [] -> seq [e]
    match xs with
    | x::xs -> permute xs (Value x)
    | [] -> Seq.empty

let findBest xs =
    let best,result =
        genExprs xs
        |> Seq.map (fun e -> e,eval e)
        |> Seq.maxBy snd
    toString best + " = " + string result

findBest [-3; -4; 5]
退货 "-3 * -4 * 5 = 60"

findBest [0; 10; -4; 0; 52; -2; -40]
退货 "0 - 10 * -4 + 0 + 52 * -2 * -40 = 4200"