1. Let A[1 .. n] be an array/sequence. Recall from lecture that a subsequence of A is any sequence obtained by extracting elements from A in order; the elements need not be contiguous in A. For example, the strings C, DAM, YAIOAI, and DYNAMICPROGRAMMING are all subsequences of DYNAMIC PROGRAMMING. The sequence(5,9,4) is a subsequence of 1, 5, 45, 9, 34, 42, 46) Call a sequence X[1 .. n] of numbers weakly bitonic if there is an index i with 1 n, such that the prefix X[1i] is increasing and the suffixx(i.. n] is decreasing In other words, X[1] X[i + 1] > .. > X[n]. Both (3, 56, 92, 34,0,-5) and 45, 23,1) are weakly bitonic. Describe and analyze an O(n2) time algorithm to compute the length of the longest weakly bitonic subsequence of an arbitrary array A of integers. Your analysis should explain how much time and space you:r algorithm uses