Please follow the given format below to answer this question. 1. Let A[1. n] be
ID: 3870709 • Letter: P
Question
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[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.Explanation / Answer
int weaklyBitonic(int A[], int n)
{
int incA[n]; // Length of increasing subarray ending at all indexes
int decA[n]; // Length of decreasing subarray starting at all indexes
int i, max;
// length of increasing sequence ending at first index is 1
incA[0] = 1;
// length of increasing sequence starting at first index is 1
decA[n-1] = 1;
//Increasing sub array
for (i = 1; i < n; i++)
incA[i] = (A[i] >= A[i-1])? incA[i-1] + 1: 1;
//Decreasing subarray
for (i = n-2; i >= 0; i--)
decA[i] = (A[i] >= A[i+1])? decA[i+1] + 1: 1;
max = incA[0] + decA[0] - 1;
for (i = 1; i < n; i++)
if (incA[i] + decA[i] - 1 > max)
max = incA[i] + decA[i] - 1;
return max;
}
Recurisve pseudo code for increasing array and decreasing array:
incArray(prev,A[1..n]):
if n=0
return 0
else
max1incArray(prev,A[2..n])
if A[1] > prev
L1+incA(A[1],A[2..n])
if L > max1
max1<- L
return max1
decArray(prev,A[1..n]):
if n=0
return 0
else
max2LISbigger(prev,A[2..n])
if A[1] < prev
L1+LISbigger(A[1],A[2..n])
if L > max2
max2<- L
return max2