Longest alternating subsequence

A sequence {x1, x2, .. xn} is alternating sequence if its elements satisfy one of the following relations :

  x1 < x2 > x3 < x4 > x5 < …. xn or 
  x1 > x2 < x3 > x4 < x5 > …. xn

Examples:

Input: arr[] = {1, 5, 4}
Output: 3
The whole arrays is of the form  x1 < x2 > x3 

Input: arr[] = {1, 4, 5}
Output: 2
All subsequences of length 2 are either of the form 
x1 < x2; or x1 > x2

Input: arr[] = {10, 22, 9, 33, 49, 50, 31, 60}
Output: 6
The subsequences {10, 22, 9, 33, 31, 60} or
{10, 22, 9, 49, 31, 60} or {10, 22, 9, 50, 31, 60}
are longest subsequence of length 6.

Below is recursive structure in the problem.

lookup[i][0] = Length of the longest Zig-Zag 
               subsequence ending at index i 
               and last element is greater
               than its previous element
lookup[i][1] = Length of the longest Zig-Zag 
               subsequence ending at index i 
               and last element is smaller
               than its previous element

Recursive Formulation:
 lookup[i][0] = max (lookup[i][0], lookup[j][1] + 1); 
                for all j < i and arr[j] < arr[i] 
 lookup[i][1] = max (lookup[i][1], lookup[j][0] + 1); 
             for all j < i and arr[j] > arr[i]

In this post, a memoization based solution is discussed.

// C++ program to find length of the longest
// alternating subsequence.
#include <bits/stdc++.h>
using namespace std;

// define max number of elements in array
#define N 10

// lookup table to store solutions of subproblem
// max(lookup[i][0], lookup[i][1]) stores longest
// sequence till arr[0..i]
int lookup[N][2];

// Util function to find length of longest subsequence
// if flag is true, next element should be greater
// if flag is false, next element should be smaller
int Util(int arr[], int start, int end, bool flag)
{
    // If already solved
    if (lookup[start][flag] != 0)
        return lookup[start][flag];

    // if sub-problem is seen for the first time,
    // solve it and store its result in lookup table
    int res = 0;
    for (int i = start; i <= end; i++)
    {
        // include arr[i] as next high in subsequence
        // and flip flag for next subsequence
        if (flag && arr[i - 1] < arr[i])
            res = max(res, 1 + Util(arr, i + 1, end, !flag));

        // include arr[i] as next low in subsequence and
        // flip flag for next subsequence
        else if (!flag && arr[i - 1] > arr[i])
            res = max(res, 1 + Util(arr, i + 1, end, !flag));

        // don't include arr[i] in subsequence
        else
            res = max(res, Util(arr, i + 1, end, flag));
    }

    lookup[start][flag] = res;

    // return solution to current sub-problem
    return lookup[start][flag];
}

// Function to find length of longest subsequence
// with alternate low and high elements. It uses
// Util() method.
int findLongestSequence(int arr[], int n)
{
    // Fix first element and recurse for remaining
    // elements. There are two possibilities -

    // 1. Next element is greater (pass true)
    // 2. Next element is smaller (pass false)
    return 1 + max(Util(arr, 1, n - 1, true),
                   Util(arr, 1, n - 1, false));
}

// main function
int main()
{
    int arr[] = { 8, 9, 6, 4, 5, 7, 3, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findLongestSequence(arr, n);
    return 0;
}

Output:

6

Time complexity : O(n2)
Auxiliary Space : O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/longest-alternating-subsequence/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar