Greedy: Given an array, find the longest alternative subsequence

Problem Statement:

You are given an array, you need to find the longest alternative sub-sequence.

Alternative sub-sequence is a sequence where the difference between the number alternates between positive and negative.

You need to find the longest of such sub-sequence

Example:

Input: arr = [1, 6, 4, 8, 3, 6]
Output: 6

Explanation:

[5, -2, 4, -5, 3] is the sub-sequence.

Solution Explanation:

We will use greedy approach to solve t he problem.

We greedily check the difference between 2 numbers.

If they differ then update the count, else we skip.

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

Code Solution

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


int solution(vector<int>& nums) 
{
    if(nums.size()==1)
        return 1;
        
    int prev_diff = nums[1] - nums[0];  
    int counter = (prev_diff != 0) ? 2 : 1; 
    
    for(int i=2; i<nums.size(); i++) 
    {
        int curr_diff = nums[i] - nums[i-1];
        
        if((curr_diff > 0 && prev_diff <= 0) || 
           (curr_diff < 0 && prev_diff >= 0)) 
        {
            counter++;
            prev_diff = curr_diff;
        }
    }
    
    return counter;
}
int main() 
{
    vector<int> arr = {1, 6, 4, 8, 3, 6};

    cout <<solution(arr);
}

Output

6