An algorithm to bracket an expression to maximize its value

Question

I found this when looking for problems with dynamic programming. You are given a non-parameterized expression of the form V0 O0 V1 O1 .... Vn-1

We need to put brackets in places that maximize the meaning of the whole expression.

V are operands, and O are operators. In the first version, problematic operators can be * and +, and operands are positive. The second version of the problem is completely general.

For the first version, I came up with a DP solution.

Solution - A [] = array of operands B [] - array of operators T (A [i, j]) - the maximum value of the expression T (A [0, n-1]) = max for 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 is a better one.

Answer 1

It is easier to analyze the calculations of elements A[i,j] from shorter ranges to longer ranges. The algorithm for this is as follows:

 # 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 a constant access time (array) than the O(n^3) algorithm.