Longest Alternating Subsequence Problem (with Solution)

The LAS problem involves finding the length of the longest sub-subsequence where the elements alternate in either increasing or decreasing order. In this article, we will learn more about the Longest Alternating Subsequence problem and discuss its practical applications.

Longest Alternating Subsequence Problem

The Longest Alternating Subsequence is the longest sequence within a given sequence, where the elements alternate in either ascending or descending order. The subsequence need not be contiguous, and elements can be skipped while preserving the alternating pattern.

Let's take an example!

Given the sequence: [5, 2, 9, 7, 11, 12, 13, 8]

To find the longest alternating subsequence within this sequence, we aim to identify the elements that alternate in either ascending or descending order.

We can solve the Longest Alternating Subsequence problem using a dynamic programming approach.

1. Create an array to store the lengths of the longest alternating subsequences up to each index of the input sequence.

2. Initialize all elements of the array to 1, as each element can be considered as a subsequence of length 1.

   [1, 1, 1, 1, 1, 1, 1]

3. Iterate through the input sequence starting from the second element.

   For each element num at the index i in the input sequence:

   • Compare num with the previous element.
   • If num is greater than the previous element and the length of the longest alternating subsequence ending at the previous index is even, update the length at the index i in the array to be one more than the length at the previous index.
   • If num is smaller than the previous element and the length of the longest alternating subsequence ending at the previous index is odd, update the length at the index i in the array to be one more than the length at the previous index.
   • Otherwise, the length at index i remains the same as the length at the previous index.

   After iterating through the sequence, the array will store the lengths of the longest alternating subsequences up to each index.

   [1, 2, 3, 4, 5, 2, 2, 6]

4. The maximum value in the array represents the length of the longest alternating subsequence. In this case, the maximum value is 6.

The longest alternating subsequence in the given sequence is [5, 2, 9, 7, 11, 12, 13, 8], where the elements alternate between ascending and descending order.as 5>2<9>7<11>8

Dynamic Programming Approach

The most commonly used approach to solve the Longest Alternating Subsequence problem is through dynamic programming.

The algorithm utilizes an array to store the lengths of the longest alternating subsequences up to each index of the input sequence. By iteratively filling in this array, we can find the length of the longest alternating subsequence. Let us take a look at the code for the same.

#include <iostream>
#include <vector>
using namespace std;

int dynamicLAS(const vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(2, 1)); // dp[i][0] for increasing, dp[i][1] for decreasing

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[i] > arr[j]) {
                dp[i][0] = max(dp[i][0], dp[j][1] + 1);
            } else if (arr[i] < arr[j]) {
                dp[i][1] = max(dp[i][1], dp[j][0] + 1);
            }
        }
    }

    int maxLen = 1;
    for (int i = 0; i < n; ++i) {
        maxLen = max(maxLen, max(dp[i][0], dp[i][1]));
    }

    return maxLen;
}

int main() {
    vector<int> arr = {5, 2, 9, 7, 11, 12, 13, 8};
    cout << "Length of the longest alternating subsequence: " << dynamicLAS(arr) << endl;

    return 0;
}

Output:

Length of the longest alternating subsequence: 6

The time complexity of the dynamic programming approach is O(n^2), where n is the number of elements in the input array. The space complexity is O(n).

Recursive Approach

The problem can also be solved recursively by considering each element in the sequence as a potential part of the longest alternating subsequence. The recursion explores all possible combinations and selects the one with the maximum length. However, this approach can be computationally expensive, particularly for larger sequences.

Let us understand this approach better with the code:

#include <iostream>
#include <vector>
using namespace std;

int recursiveLAS(const vector<int>& arr, int prev, int current, bool isIncreasing) {
    if (current == arr.size()) {
        return 0;
    }

    int includeCurrent = 0;
    if ((isIncreasing && arr[current] > prev) || (!isIncreasing && arr[current] < prev)) {
        includeCurrent = 1 + recursiveLAS(arr, arr[current], current + 1, !isIncreasing);
    }

    int excludeCurrent = recursiveLAS(arr, prev, current + 1, isIncreasing);

    return max(includeCurrent, excludeCurrent);
}

int longestAlternatingSubsequence(const vector<int>& arr) {
    if (arr.empty()) {
        return 0;
    }

    return 1 + max(recursiveLAS(arr, arr[0], 1, true), recursiveLAS(arr, arr[0], 1, false));
}

int main() {
    vector<int> arr = {5, 2, 9, 7, 11, 12, 13, 8};
    cout << "Length of the longest alternating subsequence: " << longestAlternatingSubsequence(arr) << endl;

    return 0;
}

Output:

Length of the longest alternating subsequence: 6

The time complexity of the recursive approach can be exponential, O(2^n), where n is the number of elements in the input array. The space complexity is O(n), where n is the number of elements in the input array.

Applications of the LAS Problem

Here are some of the practical applications of this problem in the real world:

• Financial Analysis: You can use it to find and analyze stock price patterns. By identifying the longest alternating subsequence within a series of price changes, analysts can gain insights into trends.

• Data Compression: By removing elements that do not conform to the alternating pattern, the compressed data retains the key information while reducing redundancy.

• Pattern Recognition: The Longest Alternating Subsequence problem finds applications in pattern recognition tasks, such as speech recognition and gesture recognition. 

Conclusion

By leveraging the solutions to the Longest Alternating Subsequence problem, researchers and practitioners can extract meaningful patterns, optimize data representation, and make informed decisions across diverse domains.