Algorithm to bracket an expression in order to maximize its value

Question

I found this while looking up problems on dynamic programming. You are given an unparanthesized expression of the form V0 O0 V1 O1 .... Vn-1

We have to put brackets at places which maximizes the value of the entire expression.

V's are the operands and O's are the operators. In the first version of problem operators can be * and + and operands are positive. Second version of problem is completely general.

For the first version i came up with DP solution .

Solution - A[] = operands array B[] - operators array T(A[i,j]) - max value of expression T(A[0,n-1]) = max over all i {(T(A[0,i]) Oi T(A[i+1,n-1]))}

The boundary cases are trivial (when i = j). I need help with the following - Analyze the running time of this algorithm. And if there exists a better one.

Crispate

Reffer to Thomas H. Cormen - Introduction to Algorithms, Chapter - Dynamic Programming. You wouldn't find better explanation anywhere. – Divisionism

Answer 1

It is easier to analyze calculation of A[i,j] elements from shorter ranges to longer ranges. Algorithm for that looks like:

# Initialization of single values
for i in 0, ..., n-1:
  A[i,i] = V[i]

# Iterate through number of operation
for d in 1, ..., n-1:
  # Range start
  for i in 0, ..., n-1-d:
    j = i + d
    A[i,j] = max( A[i,x] O_x A[x+1,j] for x in i, ..., j-1)

print 'Result', A[0,n-1]

Since A[] can be implemented with constant time access (array) than algorithm is O(n^3).

Adamis

I think that in general version of the problem we should also process the min value, because the result of min * min is max. So we should keep two dynamic programming arrays. – Lock