376 Wiggle Subsequence
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.
For example, [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,4,7,2,5]
and [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.
Examples:


Follow up:
Can you do it in O(n) time?
思路
利用贪心的方法可以做。
譬如[1,7,4,9,2,5]
这个数组，差值数组为[6,3,5,7,3]
。 如果差值是[6,3,5,6,1,6,3,1,5,7,3]
，我们就可以把前面的六个正数看成一个正数，两个负数看成一个负数，以此类推，统计最终合并后的元素个数即可。

