Wiggle Subsequence


Time complexity analysis for approach 1:
Since T(n) = 2[T(n  1) + T(n  2) + ... + T(1)], (1)
then T(n  1) = 2[T(n  2) + T(n  3) + ... + T(1)], (2)
which is T(n  2) + T(n  3) + ... + T(1) = (1/2) * T(n  1), (3)
from (1) and (3), we can get
T(n) = 2[T(n  1) + (1/2) * T(n  1)]
= 3 * T(n  1)
= (3^2) * T(n  2)
.
.
.
= 3 ^ (n  1) * T(1).
And because of T(1) = 1, we can get T(n) = (1/3) * 3^n, (4)
then we can say the time complexity is O(3^n).And from (4), T(n) >= (1/3) (2^n) = O(2^n).
In summary, we can say approach #1 is exponential time.

Hi, LASkuma. I volunteer to give a proof of the correctness of approach #3. Sorry I didn't notice that I make it so long :)
#3 Approach
From the approach, we can see it considers the maximum of the last elements of up array
and down array as the result.The prove the approach is correct, we need to prove that "the maximum of the last elements
of up array and down array as the result".This is equivalent to prove "the last element of a sequence would also be the last element
of one of its longest wiggle sequence".  (1)Proof by mathematical induction:
Basis:
(1) is naturally valid for sequences of size 1.
Inductive step:
Assume (1) is valid for any sequences of size k, where k >= 1.  (2)
Then considering a sequence of size (k + 1). We label it as A, that is {nums[1], nums[2], ...,
nums[k], nums[k + 1]}).A's subsequence, which consists of first k elements, also satisfy (1). We label it as B,
that is {nums[1], nums[2], ..., nums[k]}.Assume C is one of B's longest wiggle subsequences. C has nums[k] as its last element.
Then there are there cases to consider:Case 1: nums[k] is in up wiggle, there are two cases for nums[k]:
Case 1.1: nums[k] <= nums[k + 1]
nums[k + 1] would keep the up wiggle continue. Therefore, replacing nums[k]
with nums[k + 1] in C would result in a longest wiggle subsequence for A.
Case 1.2: nums[k] > nums[k + 1]
nums[k + 1] would stop the up wiggle, and starts a down wiggle. Therefore,
appending nums[k + 1] to C would result in a longest wiggle subsequence for A.Case 2: nums[k] is in down wiggle,
Case 2.1: nums[k] >= nums[k + 1]
nums[k + 1] would keep the down wiggle continue. Therefore, replacing nums[k]
with nums[k + 1] in C would result in a longest wiggle subsequence for A.
Case 2.2: nums[k] < nums[k + 1]
nums[k + 1] would stop the down wiggle, and starts an up wiggle. Therefore,
appending nums[k + 1] to C would result in a longest wiggle subsequence for A.Case 3: nums[k] is not in any wiggle.
Case 3.1: nums[k] = nums[k + 1]
nums[k + 1] would still make no wiggle. Therefore, replacing nums[k]
with nums[k + 1] in C would result in a longest wiggle subsequence for A.
Case 3.2: nums[k] < nums[k + 1]
nums[k + 1] would start an up wiggle. Therefore, appending nums[k + 1] to C
would result in a longest wiggle subsequence for A.
Case 3.3: nums[k] > nums[k + 1]
nums[k + 1] would start a down wiggle. Therefore, appending nums[k + 1] to C
would result in a longest wiggle subsequence for A.From all these cases, we can say that nums[k + 1] is the last element of one of A's longest
wiggle subsequence.Proved.


We can do it a more short way
int wiggleMaxLength(vector<int>& nums) { if (nums.size() < 2) return nums.size(); int p = 0, len = 1; for (int i = 0; i < nums.size()1; ++i) { if (nums[i] == nums[i+1]) continue; if ((nums[i]nums[p])*(nums[i+1]nums[i]) <= 0) p = i, ++len; } return len;
}

This might be mich easier than the methods given above:
Logic  We just need to be going forward until a desirable difference is found, and then repeat with that difference.int mlength=n,diff=0; for(int i=1; i<n;i++){ if(nums[i]==nums[i1]) mlength; else if(nums[i]nums[i1]>0 && diff<=0  nums[i]nums[i1]<0 && diff>=0) diff=nums[i]nums[i1]; else mlength; } return mlength;

Approach #5 in Ruby follows.
def longest_wiggle(arr) arr.each_cons(2). reject { a,b a==b }. map(&:first). push(arr.last). each_cons(3). select { triple [triple.min, triple.max].include? triple[1] }. map { _,n,_ n }. unshift(arr.first). push(arr.last) end
The first four lines (through
push(arr.last).
) are to convert each sequence of adjacent equal values to one instance of the value (e.g.,[1,2,2,2,3,4,4,] => [1,2,3,4]
). If the data contain no such sequences those lines can be removed and the next line changed toarr.each_cons(3).
.

Chidong, you asked, "Is there any case that the longest subsequence does not contains the 1st element?". Suppose the first two elements of a longest subsequence are at indices
i > 0
andj > i
. Suppose further thatx(i) > x(j)
. Ifx(k) < x(i)
for anyk < i
, a longer subsequence could be obtained by starting atx(k)
, a contradiction. That impliesx(i1) >= x(i)
, which contradicts the assumption thatx(i)
is a peak or valley bottom. A similar argument can be made whenx(i) < x(j)
. It follows that all longest subsequences must begin with the first element of the array, and, by a similar argument, end with the last element of the array.

@swoveland you probably should add another
each_cons(2).reject{a,b a==b }.map(&:first).push(arr.last)
at the end because you could end up with an array
[x,x]
where the first and last element ofarr
are the same (x
) and you would not pass.

@momolog, I don't understand how one could end up with
[x,x]
. If the array has no wiggles (e.g., all values equalx
), an empty array would be returned. If the first and last values arex
and at least one value is notx
, there would be at least one wiggle, meaning that the array returned would have at least three elements. No? Could you give an example? Can you or someone else give me a link that explains how comments and answers are to be formatted on leetcode?

@swoveland you can pass e.g.
[2,2]
or[2,2,2]
to your method, which will both return[2,2]
, which is clearly not a wiggle sequence. It is because you are removing duplicate consecutive pairs in the first step  but in the last step unshift and push two elements that might be equal.As for formatting: it's standard markdown: either enclose your code block in a pair of ``` or indent all lines with 4 spaces.

@momolog, thanks for pointing that out. How about adding this at the beginning of the method:
return [] if arr.uniq.size == 1
.

class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums == null  nums.length == 0) {
return 0;
}
final int UP = 0;
final int DOWN = 1;
final int START = 2;
int state = START;
int res = 1;
for (int i = 0; i < nums.length  1; i++) {
switch(state) {
case START:
if (nums[i] < nums[i + 1]) {
state = UP;
res++;
} else if (nums[i] > nums[i + 1]) {
state = DOWN;
res++;
}
break;
case UP:
if (nums[i] <= nums[i + 1]) {
state = UP;
} else {
state = DOWN;
res++;
}
break;
case DOWN:
if (nums[i] < nums[i + 1]) {
state = UP;
res++;
} else {
state = DOWN;
}
break;
}} return res; }
}
Complexity Analysis
Time complexity : O(n). We traverse the given array once.
Space complexity : O(1). No extra space is used.

class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums == null  nums.length == 0) {
return 0;
}
final int UP = 0;
final int DOWN = 1;
final int START = 2;
int state = START;
int res = 1;
for (int i = 0; i < nums.length  1; i++) {
switch(state) {
case START:
if (nums[i] < nums[i + 1]) {
state = UP;
res++;
} else if (nums[i] > nums[i + 1]) {
state = DOWN;
res++;
}
break;
case UP:
if (nums[i] <= nums[i + 1]) {
state = UP;
} else {
state = DOWN;
res++;
}
break;
case DOWN:
if (nums[i] < nums[i + 1]) {
state = UP;
res++;
} else {
state = DOWN;
}
break;
}} return res; }
}