A zig-zag sequence is a sequence A where, for every index i between 2 and |A| -

Question

A zig-zag sequence is a sequence A where, for every index i between 2 and |A| - 1, A[i] is either larger than both of its neighbors A[i - 1] and A[i + 1], or smaller than both. For example, . 1, 3, 2. 5, 4 is a zig-zag sequence, whereas 1, 2, 3. 5. 4 is not (see figure below). in this problem, your goal is find the length of the longest zig-zag subsequence of a given sequence. For example, for the sequence 1, 2, 3, 5, 4, the answer is 3 (corresponding to, e.g., 1, 5, 4). Define a recursive function for computing the length of the longest zig-zag subsequence. Your equation should lead to an efficient (polynomial time) dynamic program, but you do not need to provide the algorithm, a proof of correctness, or the running time. Please remember to give a formal definition for your recursive function(s), and include any base cases.

Explanation / Answer

// A naive C/C++ based recursive implementation of LIS problem
#include<stdio.h>
#include<stdlib.h>

// Recursive implementation for calculating the LIS
int _lis(int arr[], int n, int *max_lis_length)
{
// Base case
if (n == 1)
return 1;

int current_lis_length = 1;
for (int i=0; i<n-1; i++)
{
// Recursively calculate the length of the LIS
// ending at arr[i]
int subproblem_lis_length = _lis(arr, i, max_lis_length);

// Check if appending arr[n-1] to the LIS
// ending at arr[i] gives us an LIS ending at
// arr[n-1] which is longer than the previously
// calculated LIS ending at arr[n-1]
if (arr[i] < arr[n-1] &&
current_lis_length < (1+subproblem_lis_length))
current_lis_length = 1+subproblem_lis_length;
}

// Check if currently calculated LIS ending at
// arr[n-1] is longer than the previously calculated
// LIS and update max_lis_length accordingly
if (*max_lis_length < current_lis_length)
*max_lis_length = current_lis_length;

return current_lis_length;
}

// The wrapper function for _lis()
int lis(int arr[], int n)
{
int max_lis_length = 1; // stores the final LIS

// max_lis_length is passed as a reference below
// so that it can maintain its value
// between the recursive calls
_lis( arr, n, &max_lis_length );

return max_lis_length;
}

// Driver program to test the functions above
int main()
{
int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of LIS is %d ", lis( arr, n ));
return 0;
}

// A naive Java based recursive implementation of LIS problem
class LIS
{
static int max_lis_length; // stores the final LIS

// Recursive implementation for calculating the LIS
static int _lis(int arr[], int n)
{
// base case
if (n == 1)
return 1;

int current_lis_length = 1;
for (int i=0; i<n-1; i++)
{
// Recursively calculate the length of the LIS
// ending at arr[i]
int subproblem_lis_length = _lis(arr, i);

// Check if appending arr[n-1] to the LIS
// ending at arr[i] gives us an LIS ending at
// arr[n-1] which is longer than the previously
// calculated LIS ending at arr[n-1]
if (arr[i] < arr[n-1] &&
current_lis_length < (1+subproblem_lis_length))
current_lis_length = 1+subproblem_lis_length;
}

// Check if currently calculated LIS ending at
// arr[n-1] is longer than the previously calculated
// LIS and update max_lis_length accordingly
if (max_lis_length < current_lis_length)
max_lis_length = current_lis_length;

return current_lis_length;
}

// The wrapper function for _lis()
static int lis(int arr[], int n)
{
max_lis_length = 1; // stores the final LIS

// max_lis_length is declared static above
// so that it can maintain its value
// between the recursive calls of _lis()
_lis( arr, n );

return max_lis_length;
}

// Driver program to test the functions above
public static void main(String args[])
{
int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
int n = arr.length;
System.out.println("Length of LIS is " + lis( arr, n ));
}

} // End of LIS class.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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