(a) Callasequence X [1.. n ] oscillating if X [ i ]< X [ i +1]foralleven i ,and

Question

(a) CallasequenceX[1..n]oscillatingifX[i]<X[i+1]foralleveni,andX[i]>X[i+1] for all odd i. Give a simple recursive definition for the function los(A), which gives the length of the longest oscillating subsequence of an arbitrary array A of integers.

(b) Give a simple recursive definition for the function sos(A), which gives the length of the shortest oscillating supersequence of an arbitrary array A of integers.

(c) CallasequenceX[1..n]acceleratingif2·X[i]<X[i 1]+X[i+1]foralli. Give a simple recursive definition for the function lxs(A), which gives the length of the longest accelerating subsequence of an arbitrary array A of integers.

Explanation / Answer

(A) Length of Longest oscillating subsequence of an arbitrary array

#include<bits/stdc++.h>
using namespace std;

// Returns the length and the LOS of two
// arrays arr1[0..n-1] and arr2[0..m-1]
int LOS(int arr1[], int n, int arr2[], int m)
{
// table[j] is going to store length of LOS
// ending with arr2[j]. We initialize it as 0,
int table[m];
for (int j=0; j<m; j++)
table[j] = 0;

// Traverse all elements of arr1[]
for (int i=0; i<n; i++)
{
// Initialize current length of LOS
int current = 0;

// For each element of arr1[], trvarse all
// elements of arr2[].
for (int j=0; j<m; j++)
{
// If both the array have same elements.
if (arr1[i] == arr2[j])
if (current + 1 > table[j])
table[j] = current + 1;

/* Now seek for previous smaller common
element for current element of arr1 */
if (arr1[i] > arr2[j])
if (table[j] > current)
current = table[j];
}
}

// The maximum value in table[] is out result
int result = 0;
for (int i=0; i<m; i++)
if (table[i] > result)
result = table[i];

return result;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.