Assume that the cost of multiplying an array A, with size x×y, and an array B, with size y×z, costs xyz, and results in an array of size x×z. Now consider the problem of multiplying the sequence of arrays A_{1}A_{2}A_{3}…A_{n}. Each array A_{i} has size p_{i-1}×p_{i}. Although these multiplications could be performed in any order (due to associative property of the multiplication), the order in which we perform these multiplications can have an effect on the cost. For example, assume arrays A_{1}A_{2}A_{3} with sizes 10×100, 100×5, and 5×50. The multiplication (A_{1}A_{2})A_{3} costs 10⋅100⋅5+10⋅5⋅50=7500, while the multiplication A_{1}(A_{2}A_{3}) costs 100⋅5⋅50+10⋅100⋅50=75000.
Using dynamic programming, given a set of sizes p_{i}, find the best parenthesization of the matrices (i.e., find in which order the arrays should be multiplied). Hint: look at the last multiplication of the optimal result, and its operands as its subproblems.
For instance, if A = (1, 9, 17, 5, 8, 6, 4, 7, 12, 3), then both (1, 9, 17) and (1, 5, 6, 7, 12) are increasing subsequences. Note that the subsequence given by the greedy algorithm, that is the subsequence (1, 9, 17), is not the longest one.
In order to find the longest increasing subsequence in the array, you can compute for each position i the length L[i] of the longest subsequence that ends with element A[i].