Longest alternating subsequence

You are given an array arr. Your task is to find the longest length of a good sequence. A good sequence {x1, x2, .. xn} is an alternating sequence if its elements satisfy one of the following relations :

1.  x1 < x2 > x3 < x4 > x5. . . . . and so on
2.  x1 >x2 < x3 > x4 < x5. . . . . and so on

Examples:

Input: arr= [1, 5, 4]
Output: 3
Explanation: The entire sequenece is a good sequence.

Input: arr= [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
Output: 7
Explanation: There are several subsequences that achieve this length. 
One maximum length good subsequences is [1, 17, 10, 13, 10, 16, 8].

Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Constraints:
1 <= nums.size() <= 10⁵ 
1 <= nums[i] <= 10⁴ 

Approach01:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int alternatingMaxLength(vector<int>& arr) {
        int n = arr.size();
        if (n == 0) {
            return 0;
        }
        
        // Initialize variables to keep track of the longest lengths
        int inc_length = 1;
        int dec_length = 1;
        
        // Traverse the array to update the lengths
        for (int i = 1; i < n; ++i) {
            if (arr[i] > arr[i - 1]) {
                inc_length = dec_length + 1;
            } else if (arr[i] < arr[i - 1]) {
                dec_length = inc_length + 1;
            }
        }
        
        return max(inc_length, dec_length);
    }
};

class Solution:
    def alternatingMaxLength(self, arr):
        n = len(arr)
        if n == 0:
            return 0
        
        # Initialize variables to keep track of the longest lengths
        inc_length = 1
        dec_length = 1
        
        # Traverse the array to update the lengths
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                inc_length = dec_length + 1
            elif arr[i] < arr[i - 1]:
                dec_length = inc_length + 1
        
        return max(inc_length, dec_length)

Time Complexity

• Initialization:

  Initializing variables inc_length and dec_length takes \( O(1) \) time.

• Traversal of the Array:

  Traversing the array once from index 1 to \( n-1 \) takes \( O(n) \) time, where \( n \) is the size of the arr vector.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Space:

  The algorithm uses a constant amount of extra space for the variables inc_length and dec_length, resulting in \( O(1) \) space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).