2. (1 12 points) Recall the longest increasing subsequence problem discussed in class. Given a sequence of integers in an array A = A[1], ..., A[n], design an algorithm to find the length of the longest increasing subsequence and one such subsequence. In the class, we defined a quantity Li) which was the length of the longest increasing subsequence that ends with the ith integer A[i]. For this question, we define the quantity S(i) to be the length of the longest increasing subsequence that starts with the ith integer A[i]. (a) Give the recursive formulation for S(i) including an appropriate base case. (b) Use the above recursive formulation to design an algorithm that returns the length of the longest increasing subsequence. Give pseudocode and discuss running time. (c) Make appropriate modifications/additions to your algorithm in part (b) to design an algorithm that outputs a longest increasing subsequence. Give pseudocode and discuss running time. 2. (1 12 points) Recall the longest increasing subsequence problem discussed in class. Given a sequence of integers in an array A = A[1], ..., A[n], design an algorithm to find the length of the longest increasing subsequence and one such subsequence. In the class, we defined a quantity Li) which was the length of the longest increasing subsequence that ends with the ith integer A[i]. For this question, we define the quantity S(i) to be the length of the longest increasing subsequence that starts with the ith integer A[i]. (a) Give the recursive formulation for S(i) including an appropriate base case. (b) Use the above recursive formulation to design an algorithm that returns the length of the longest increasing subsequence. Give pseudocode and discuss running time. (c) Make appropriate modifications/additions to your algorithm in part (b) to design an algorithm that outputs a longest increasing subsequence. Give pseudocode and discuss running time