UNB/ CS/ David Bremner/ teaching/ cs3383/ tests/ solutions-t2
• Given a sequence of nonzero integers, the longest alternating subsequence is the longest subsequence such that succesive elements of the subsequence change sign. For example given the sequence

``````1, 7, −3, −4, 5, 7, −9,
``````

a (non-unique) longest alternating subsequence is 7, −3, 5, −9. We interested here in computing the length of the longest alternating subsequence.

• What are the subproblems?

Let the input be `a₁̣…aₙ`. Define `L[j]` as the length longest alternating subsequence in `a₁…aⱼ`.

• Give a recurrence suitable for a dynamic programming algorithm.

L[i] = max { L[j] + δ(i,j) ∣ j < i}

where `δ(i,j)=1` if `aⱼ·aᵢ < 0`, 0 otherwise.

Base case: `L[1]=1`

• Describe and analyze a dynamic programming algorithm to find an optimal binary search tree for a given set of integers.

For a complete solution, see section 5.7 in Jeff Erickson's notes.

The main idea is to look at solutions for an interval in the sorted frequency array. Within each interval we recurse by choosing all possible roots.