Your array can be abstracted like this:
solution LC376
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) :)
Your array can be abstracted like this:
solution LC376
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) :)
Thanks! I wrote the code based on your idea.
https://discuss.leetcode.com/topic/54947/count-the-turning-points-no-dp-no-greedy