= Problem 2 (Rollercoaster Sequences). (30 points) You are given a sequence of numbers a[1..n). A rollercoaster sequence of level k b[1..m] is a subsequence of a that can be decomposed into at most k segments (where neighboring segments share exactly one number), where the segments alternate between increasing and decreasing. For example, if a[] = {1,5, 4, 7, 2,8, 3, 9, 10,6}, a rollercoaster sequence of level 3 can be b[] = {1,4, 7, 2, 9, 10}, it can be decomposed into three seg- ments {1,4,7}, {7, 2}, {2, 9, 10}, which are increasing, decreasing and increasing respectively. For this problem, the segments are allowed to have length 1, so that {5, 4, 7, 9, 10} is also a valid roller- coaster sequence (its decomposition is {5}, {5,4}, {4, 7, 9, 10}). The first component should always be increasing. Given a seuqnce of numbers a[1..n) and k, find the length of the longest rollercoaster sequence of level k. (a) (12 points) Define the state (sub-problems), write the transition function, and specify the base cases. (b) (10 points) Design an algorithm for the Rollercoaster Sequences problem. (c) (8 points) Prove the correctness of your algorithm