通过括号 - 算法表达的最大结果

Question

我的表达式由用加号和减号分隔的数字组成.我需要在数字之间加上大括号来获得这个表达式的最大结果.我正在尝试为这个问题得到多项式算法,但我需要一些建议或提示如何实现它.我在这里发现了类似的东西,但我不知道如何修改它.

编辑:我认为这个想法可能类似于此

getMax(inp)
{ 
  if(|inp| == 1) 
    return inp[1] // base case 
  else
    val = 0;
    for(k=2; k < |inp|; k+=2)
        val = max{val, getMax(inp[:k]) + getMax(inp[k+1:])} 
}

Answer 1

一种策略是使用动态编程来选择最后执行的最佳操作.这将表达式分为两部分.

如果操作是添加操作,则在每个部件上递归调用以查找每个部件的最大值.

如果操作是减法,则需要在第一部分找到最大值,在第二部分找到最小值.

这里有一些非memoized代码,只是为了显示重复的工作原理(注意i只迭代操作的索引,选择打破表达式的最佳位置):

import re

def T(s, f1=max, f2=min):
    if len(s) == 1: 
        return int(s[0])

    return f1(
           T(s[:i], f1, f2)+T(s[i+1:], f1, f2) 
           if s[i]=='+' else
           T(s[:i], f1, f2)-T(s[i+1:], f2, f1) 
           for i in xrange(1, len(s), 2))

def solve(expr):
    return T(re.split('([+-])', expr))

print solve('1-2+1') #0 ((1-2)+1)
print solve('1-22-23') #2 (1-(22-23))

实现自下而上的动态编程有点棘手,因为填充表格的理想顺序有点不常规.最简单的方法是使DP左右T(k, i)表示"从k操作数开始的操作数表达式的最大值/最小值i".使用在分离运算符和数字的匿名想法O和N分别的示例代码将是:

import re

def T(O, N):
    n1 = len(N)+1 #maximum expression length

    Tmax = [[float('-Inf')]*len(N) for _ in xrange(n1)]
    Tmin = [[float('+Inf')]*len(N) for _ in xrange(n1)]

    for i, n in enumerate(N): #only the numbers
        Tmax[1][i] = Tmin[1][i] = int(n)

    for k in xrange(2, n1):
        for i in xrange(n1-k):
            for j in xrange(1, k):
                if (O[i+j-1] == '+'):
                    Tmax[k][i] = max(Tmax[k][i], Tmax[j][i]+Tmax[k-j][i+j])
                    Tmin[k][i] = min(Tmin[k][i], Tmin[j][i]+Tmin[k-j][i+j])
                else:
                    Tmax[k][i] = max(Tmax[k][i], Tmax[j][i]-Tmin[k-j][i+j])
                    Tmin[k][i] = min(Tmin[k][i], Tmin[j][i]-Tmax[k-j][i+j])

    return Tmax[len(N)][0]

def solve(expr):
    A = re.split('([+-])', expr)
    return T(A[1::2], A[::2])

print solve('1+1') #2
print solve('1-2+1') #0 ((1-2)+1)
print solve('1-22-23') #2 (1-(22-23))