Problem Statement

A sequence {x1, x2, .. xn} is alternating sequence if its elements satisfy one of the following relations :x1 < x2 > x3 < x4 > x5..... or  x1 >x2 < x3 > x4 < x5.....Your task is to find the longest such sequence.Example 1:

Input:nums = {1,5,4}
Output:3
Explanation:The entire sequenece is a
alternating sequence.

Examplae 2:

Input:nums = {1,17,5,10,13,15,10,5,16,8}
Ooutput:7
Explanation:There are several subsequences
that achieve this length.
One is {1,17,10,13,10,16,8}.

Problem Link

Longest alternating subsequence | Practice | GeeksforGeeks

Code

class Solution {
	public:
		int AlternatingaMaxLength(vector<int>&nums){
		    int n = nums.size();
		    vector<int> dp1(n,1),dp2(n,1);
		    
		    for(int i=1;i<n;i++)
		    {
		        for(int j=0;j<i;j++)
		        {
		            if(nums[j]<nums[i] and dp1[i]<1+dp2[j])
		            {
		                dp1[i] = 1+dp2[j];
		            }
		            else if(nums[j]>nums[i] and dp2[i]<1+dp1[j])
		            {
		                dp2[i] = 1+dp1[j];
		            }
		        }
		    }
		    return max(*max_element(dp1.begin(),dp1.end()),*max_element(dp2.begin(),dp2.end()));
		}

};
// Time Complexity : O(n^2)

Optimized Solution

In the above approach, at any moment we are keeping track of two values (Length of the longest alternating subsequence ending at index i, and last element is smaller than or greater than previous element), for every element on array. To optimise space, we only need to store two variables for element at any index i.

inc = Length of longest alternative subsequence so far with current value being greater than it’s previous value.dec = Length of longest alternative subsequence so far with current value being smaller than it’s previous value.The tricky part of this approach is to update these two values.

“inc” should be increased, if and only if the last element in the alternative sequence was smaller than it’s previous element.

“dec” should be increased, if and only if the last element in the alternative sequence was greater than it’s previous element.

int AlternatingaMaxLength(vector<int>&nums){
		   
		   int n = nums.size();
		   int inc=1,dec=1;
		  
		   
		   for(int i=1;i<n;i++)
		   {
		       if(nums[i]>nums[i-1])
		       inc = dec+1;
		       
		       else if(nums[i]<nums[i-1])
		       dec = inc+1;
		   }
		   
		   return max(inc,dec);
		}
   
// Time Complexity : O(n)