Dynamic Programming - "maximize" matrix chain multiplication

Question

I'm now practice dynamic programming by myself. For the classic problem "matrix-chain multiplication" is to find the minimize number of scalar multiplication. Which is,

M[i,j] = 0 if i=j
       = Min(i<=k<j){M[i,k-1]+M[k,j]+Pi-1*Pj*Pk}
and its time complexity is O(n^3)

But I'm just curious what if I want to find the "maximization"(instead of min) of scalar multiplication, does it exist a optimal structure and is it possible to solve it in polynomial time?

Answer 1

The exact same reasoning as the minimization applies:

• If you multiply a₁ ... a_i, the resulting matrix dimension does not rely on the internal parenthetization.

• It follows that that if the optimal - that is, most expensive - partition of a₁ ... a_i ... a_n is to multiply the matrices from 1 to i and from i + 1 to n, then it is composed of the optimal solutions to a₁ ... a_i and a_{i + 1} ... a_n

Since the optimal substructure remains, you can use the same algorithm as minimization (of course, changing the criteria for optimality from minimum to maximum).