Suppose that we have a sequence a₁,a₂,...,a_n that we wish to memorize. We memorize it by computing partial sums of the forms a_i + ... + a_j. Let us say that the cost of memorizing a particular integer a is |a|. The goal is to use the minimum cost to remember the partial sums so that we can reconstruct the original seqeunce. For example, if (a₁,a₂,a₃,a₄) = (1,3,2,4), one of the possible solution is to memorize:

a₁ = 1

a₂ + a₃ = 1

a₂ + a₃ + a₄ = 3

a₃ = 2

The total cost is |1| + | 1| + |3| + |2| = 7, and a₁,a₂,a₃,a₄ can be reconstructed by using Gaussian elimination from the information memorized.

Give an algorithm that computes the minimum cost to memorize a sequence a₁,a₂,...,a_n. The algorithm should be polynomial in n. (The minimum cost of the example above is 6.) (Hint: MST).