1. Let A[1 .. n] be an array/sequence. Recall from lecture that a subsequence of
ID: 3870695 • Letter: 1
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 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[1··i] is increasing and the suffixx(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 you:r algorithm uses.Explanation / Answer
**Program written in C++
Explanation and setting context from the program, the details about time and space complexity is given inline above the working section.Please go through the program line by line.
LongestBitonicSubSeq method returns the length of the Longest Bitonic Subsequence in
array of size n. This function mainly creates 2 temp arrays
incrsArray[] and decrsArray[] and returns the maximum incrsArray[i] + decrsArray[i] - 1.
incrsArray[i] ==> Longest Increasing subsequence ending with array[i]
decrsArray[i] ==> Longest decreasing subsequence starting with array[i]
----START----
//Find Longest Bitonic Subsequence using Dynamic Programming.
#include<stdio.h>
#include<stdlib.h>
int LongestBitonicSubSeq( int arr[], int n )
{
int i, j;
// Allocate memory for incrsArray[] and initialize incrsArray values as 1 for all indexes
// Auxillary space allocated --> n
int *incrsArray = new int[n];
for (i = 0; i < n; i++)
incrsArray[i] = 1;
// Compute Longest Increasing Subsequence values from left to right.
//Time complexity O(n*n). 2 nested loops used.
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && incrsArray[i] < incrsArray[j] + 1)
incrsArray[i] = incrsArray[j] + 1;
// Allocate memory for decrsArray and initialize decrsArray values as 1 for all indexes
// Auxillary space allocated --> n
int *decrsArray = new int [n];
for (i = 0; i < n; i++)
decrsArray[i] = 1;
// Compute LDS values from right to left
//Time complexity O(n*n). 2 nested loops used.
for (i = n-2; i >= 0; i--)
for (j = n-1; j > i; j--)
if (arr[i] > arr[j] && decrsArray[i] < decrsArray[j] + 1)
decrsArray[i] = decrsArray[j] + 1;
//Return the maximum value of incrsArray[i] + decrsArray[i] - 1
////Time complexity O(n). Single for loop.
int max = incrsArray[0] + decrsArray[0] - 1;
for (i = 1; i < n; i++)
if (incrsArray[i] + decrsArray[i] - 1 > max)
max = incrsArray[i] + decrsArray[i] - 1;
return max;
}
int main()
{
//Test Data
int testArr[] = {6,3,4,8,12,15,12,5,9,8,7,13,24,2,3,4,8};
int n = sizeof(testArr)/sizeof(testArr[0]);
printf("Length of Longest Bitonic Subsequence is %d ", LongestBitonicSubSeq( testArr, n ) );
return 0;
}
-----END-----
OVERALL TIME COMLEXITY- O(n2).
SPACE COMPLEXITY- O(n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.