nts) Longest alternating subsequence. Recall the longest increasing subsequence prob- lem. Now instead we want to find the maximum length subsequence that alternates increas- ing/decreasing, starting with increasing. That is, we want to find a sequence of indices n AB+1]. (a) (3 points) Given an O(n2) time algorithm for finding the length of the longest alternating subsequence using dynamic programming (b) (2 points) Show that the problem of finding the longest alternating subsequence can be formulated and solved as a shortest path on 2n vertices