Please follow the given format below to answer this question.

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 DYNAMICPROGRAMMING. The sequence (5,9,4) is a subsequence of (1,5,45,9,34,42,4,) Call a sequence X[1 .. n] of numbers weakly bitonic if there is an index 1 with 1 SiSn, such that the prefix X[1.. i] is increasing and the suffix X[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 your algorithm uses