Question

Consider a variant of the matrix-chain multiplication problem in which the goal is to parenthesize the sequence of matrices so as to maximize, rather than minimize, the number of scalar multiplications. Does this problem exhibit optimal substructure?

Answer 1

Yes, this problem does exhibit optimal substructure property. Say the highest level parenthesization splits the matrix chain into two sub chains. The parenthesization within each sub-chain must be such that they maximize the number of scalar multiplications involved for each sub chain. Let us suppose that such is not the case i.e., say that the first sub-chain could be parenthesized in another way that increases the multiplications for that sub-chain. Then we could obtain a higher number of total multiplications for the entire chain by parenthesizing the first chain in this other way. This is so because the parenthesization within one sub-chain does not affect the other chain, neither does it affect the cost of the eventual multiplication of the two sub-chains (the final multiplication cost itself depends on the matrix dimensions which are constant for a particular split point regardless of how each sub-chain is internally parenthesized). So it must be the case that when choosing from the various split points possible, the best split point can be obtained by considering, for every split point, the cost of multiplying two sub-chains and the cost of each sub-chain optimally parenthesized internal