CODEWITHSUNDEEP
algorithm
DropDropped
DropDropped

Reputation: 1273

Maximal result of expression by putting braces - algorithm

I have expression consisting of numbers separated with plus and minus sign. I need to get the maximal result of this expression by putting braces between the numbers. I'm trying to get polynomial algorithm for this problem, but I need some advice or hint how to achieve it. I've found something similar here, but I don't know how to modify it.

EDIT: I was thinking that the idea could be similar like this 

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:])} 
}

Upvotes: 2

Views: 206

Answers (2)

Juan Lopes
Juan Lopes

Reputation: 10575

One strategy is to use dynamic programming to choose the best operation to perform last. This divides the expression in two parts.

If the operation is addition, you call recursively on each part to find the maximum for each part.

If the operation is subtraction, you want to find the maximum on the first part and the minimum on the second part.

Here is some non-memoized code, just to show how the recurrence works (note that i iterates only on the indices of the operations, to choose the best place to break the expression):

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

Implementing a bottom-up dynamic programming is a little more tricky, as the ideal order to fill the table is somewhat non-conventional. The easiest way is to make the DP around T(k, i) that denotes "maximum/minimum for expressions of k operands starting at the ith operand". Using Anonymous idea of separating operators and numbers in O and N respectively, an example code would be:

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

Upvotes: 5

Paul Hankin
Paul Hankin

Reputation: 58339

Let the operators be O[0], O[1], ..., O[K-1]. Let the numbers be N[0], N[1], ..., N[K]. (There's one more number than operator).

Let M[op, i, j] be the largest value achievable from the sub-expression starting from number i and ending from number j (inclusive, both ends) if op is +, and the smallest value if op is -.

Thus M[+, 0, K] is maximum value the whole expression can take.

M satisfies a recurrence relation:

M[+, i, i] = M[-, i, i] = N[i]
M[+, i, j] = max(M[+, i, k] O[k] M[O[k], k+1, j) for k in i...j-1)
M[-, i, j] = min(M[-, i, k] O[k] M[-O[k], k+1, j) for k in i...j-1)

Here A O[k] B means A + B or A - B depending on O[k], and -O[k] means - if O[k] is +, and + if O[k] is -.

Basically, you're trying to find the best place to split the expression to either maximise or minimise the overall result. When you consider a - operator, you switch from maximising to minimising and vice versa on the right-hand-side.

These recurrence relations can be evaluated using dynamic programming in a direct way, by building a 3 dimensional table for M of size 2 * (K+1) * (K+1), where K is the number of operators.

Overall, this algorithm is O(K^3).

Upvotes: 2

Related Questions