Consider a variant of the matrixchain multiplication problem

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? Write the pseudocode for this new algorithm

Solution

Yes, this problem does exhibit optimal substructure property.

Algorithm:
->Let us consider 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 .

-> 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 internally.