A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
[1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast,
[1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Input: [1,7,4,9,2,5] Output: 6 The entire sequence is a wiggle sequence. Input: [1,17,5,10,13,15,10,5,16,8] Output: 7 There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8]. Input: [1,2,3,4,5,6,7,8,9] Output: 2
Can you do it in O(n) time?
We need to find the length of the longest wiggle subsequence. A wiggle subsequence consists of a subsequence with numbers which appears in alternating ascending / descending order.\n
Here, we can find the length of every possible wiggle subsequence and find the maximum length out of them. To implement this, we use a recursive function, which takes the array , the from which we need to find the length of the longest wiggle subsequence, boolean variable to tell whether we need to find an increasing wiggle or decreasing wiggle respectively. If the function is called after an increasing wiggle, we need to find the next decreasing wiggle with the same function. If the function is called after a decreasing wiggle, we need to find the next increasing wiggle with the same function.\n\n
To understand this approach, take two arrays for dp named and .\n
Whenever we pick up any element of the array to be a part of the wiggle subsequence, that element could be a part of a rising wiggle or a falling wiggle depending upon which element we have taken prior to it.\n
\n refers to the length of the longest wiggle subsequence obtained so far considering element as the last element of the wiggle subsequence and ending with a rising wiggle.\n
Similarly, refers to the length of the longest wiggle subsequence obtained so far considering element as the last element of the wiggle subsequence and ending with a falling wiggle.\n
\n will be updated every time we find a rising wiggle ending with the element. Now, to find , we need to consider the maximum out of all the previous wiggle subsequences ending with a falling wiggle i.e. , for every and . Similarly, will be updated.\n\n
Any element in the array could correspond to only one of the three possible states:\n
The updates are done as:\n
If , that means it wiggles up. The element before it must be a down position. So , remains the same as .\nIf , that means it wiggles down. The element before it must be a up position. So , remains the same as .\nIf , that means it will not change anything becaue it didn\'t wiggle at all. So both and remain the same as and .\n
At the end, we can find the larger out of and to find the max. wiggle subsequence length, where refers to the number of elements in the given array.\n
The process can be illustrated with the following example:\n\n
This approach relies on the same concept as Approach #3. But we can observe that in the DP approach, for updating elements and , we need only the elements and . Thus, we can save space by not using the whole array, but only the last elements.\n\n
We need not necessarily need dp to solve this problem. This problem is equivalent to finding the number of alternating max. and min. peaks in the array. Since, if we choose any other intermediate number to be a part of the current wiggle subsequence, the maximum length of that wiggle subsequence will always be less than or equal to the one obtained by choosing only the consecutive max. and min. elements.\n
This can be clarified by looking at the following figure:\n\n
From the above figure, we can see that if we choose C instead of D as the 2nd point in the wiggle subsequence, we can\'t include the point E. Thus, we won\'t obtain the maximum length wiggle subsequence.\n
Thus, to solve this problem, we maintain a variable , where is used to indicate whether the current subsequence of numbers lies in an increasing or decreasing wiggle. If , it indicates that we have found the increasing wiggle and are looking for a decreasing wiggle now. Thus, we update the length of the found subsequence when () becomes negative. Similarly, if , we will update the count when () becomes positive.\n
When the complete array has been traversed, we get the required count, which represents the length of the longest wiggle subsequence.\n\n
Time complexity : . We traverse the given array once.\n
Space complexity : . No extra space is used.\n
Analysis written by: @vinod23\n