Wiggle Subsequence In C++

In this guide, we will explore the wiggle subarray concept in C++ along with its algorithm and how to implement it.

Problem Statement:

A sequence that demonstrates strict alternating positive and negative variances between consecutive numbers is referred to as a wiggle sequence. The initial variance can be either positive or negative. Sequences containing just one element or two non-identical elements are regarded as trivially oscillating sequences.

Example 1:

Input: nums = [2,7,4,8,6,5]

Output: 6

Interpretation: The complete series represents a wiggle sequence.

Example 2:

Input: nums = [1,17,5,10,13,15,10,5,17,6]

Output: 7

Explanation: There are multiple subsequences that can attain this specific length.

Constraints :

1 <= nums.length <= 1000

0 <= nums[i] <= 1000

Concept:

• ✅ The important takeaway from this is that any number that falls in the middle of a stretch of the same direction is unnecessary. Instead, the more extreme numbers are the ones that should be kept because they increase the possibility that a subsequent number would indicate a change in direction.
• ✅ Counting the inflection points in our input array (N) where the direction changes is the straightforward solution in this case. There are a few other approaches to this, but with this function, we may monitor the direction by keeping a directional flag (up), incrementing our answer (ans), and inverting it when a change is detected.
• ✅ Setting the first direction is one difficult task. We will have to wait until we see a different number for the first time to determine our direction because the initial number can indicate any direction. Before the main loop, we can use a straightforward while loop to verify this.
• ✅ When we're done, we can return an answer.

Algorithm:

Function MaxLen(Num):
Len=length of Num
x=1
ans=1
//skip identical elements at the beginning
while x<len AND Num[x]==N[x-1]:
	x++
//If all elements are identical, return 1
if x==len
	return 1
//Determining initial direction
up=Num[x-1]>Num[x]
for each element in Num starting from index x:
	if(up AND Num[x] < Num[x-1])OR(!up AND Num[x]>Num[x-1]):
	//If the direction changes, update the direction and increment the answer
		up=NOT up
		ans++
return ans

Example:

Let's consider a scenario to demonstrate the wiggle subsequence in C++.

#include <vector>
#include<iostream>
using namespace std;
int wiggleMax(vector <int> & num) {
    int n = num.size();
    if (n < 2) return n;
    vector <int>up(n, 1); // Length of longest wiggle subsequence ending at index i, where the last two elements are increasing
    vector <int>down(n, 1); // Length of longest wiggle subsequence ending at index i, where the last two elements are decreasing
    for (int i = 1; i < n; ++i) {
        if (num[i] > num[i - 1]) {
            up[i] = down[i - 1] + 1; // If the current number is greater, we extend the sequence with up
            down[i] = down[i - 1];   // The down sequence remains the same
        } else if (num[i] < num[i - 1]) {
            down[i] = up[i - 1] + 1; // If the current number is smaller, we extend the sequence with down
            up[i] = up[i - 1];       // The up sequence remains the same
        } else {
            // If num[i] == num[i - 1], the current sequence remains the same as previous
            up[i] = up[i - 1];
            down[i] = down[i - 1];
        }
    }
    return max(up[n - 1], down[n - 1]); // Return the maximum length between the last elements of up and down
}
// Example usage:
int main() {
    vector<int> num = {1, 7, 4, 9, 2, 5};
    int result = wiggleMax(num);
    cout<<"Length of the longest wiggle subsequence "<<result<<endl;
    return 0;
}

Output:

Code explanation:

• ✅ In this example, the "wiggleMax" function takes a vector of integers 'num' as input and returns the length of the longest subsequences.
• ✅ It initializes vectors up and down to keep track of lengths of wiggle subsequences ending at each index, where up[x] represents the length ending at index x with the last two elements increasing and down[i] to show the length ending at index x with last two elements decreasing.
• ✅ It iterates through the input array, and update up and down vectors based on current
• ✅ If the current element is greater than the previous one, the up vector is updated by extending the increasing sequence, and the down vector remains the same.
• ✅ Similarly, if the current element is smaller, the down vector is updated by extending the decreasing sequence, and the up vector remains the same.
• ✅ If the current element is equal to the previous one, both sequences remain the same.
• ✅ Finally, the function returns the maximum length between the last elements of the up and down vectors.