[leetcode] 376. Wiggle Subsequence

[leetcode] 376. Wiggle Subsequence

Description

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.

Example 1:

Input:

[1,7,4,9,2,5]

Output:

6

Explanation:

The entire sequence is a wiggle sequence.

Example 2:

Input:

[1,17,5,10,13,15,10,5,16,8]

Output:

7

Explanation:

There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Example 3:

Input:

[1,2,3,4,5,6,7,8,9]

Output:

2

Follow up: Can you do it in O(n) time?

分析

题目的意思是：给定一个数组，返回其最长的摆动子序列。

维护两个数组up和down,其中up[i]表示到i位置时首差值为正的摆动子序列的最大长度；down[i]表示到i位置时首差值为负的摆动子序列的最大长度。

代码

class Solution {public: int wiggleMaxLength(vector& nums) { int n=nums.size(); if(!n){ return 0; } vector up(n,0); vector down(n,0); up[0]=down[0]=1; for(int i=1;inums[i-1]){ up[i]=down[i-1]+1; down[i]=down[i-1]; }else if(nums[i]

参考文献

​​376. Wiggle Subsequence​​​​[LeetCode] Wiggle Subsequence 摆动子序列​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。