Your array can be abstracted like this:
Consider the number of turning points: they are DIRECTLY related to the length of wiggle subsequence..
So you only need to scan once, that's O(n) :)
Good job explaining the problem in such a simple and comprehensible fashion. I got a Accepted solution but couldn't quite mathematically prove its validity. This shall do it.
Thanks! I wrote the code based on your idea.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.