wiggle-subsequence

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A wiggle sequence is a sequence where 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 one element and a sequence with two non-equal elements are trivially wiggle sequences.

<ul>
	<li>For example, <code>[1, 7, 4, 9, 2, 5]</code> is a wiggle sequence because the differences <code>(6, -3, 5, -7, 3)</code> alternate between positive and negative.</li>
	<li>In contrast, <code>[1, 4, 7, 2, 5]</code> and <code>[1, 7, 4, 5, 5]</code> are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.</li>
</ul>

A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array <code>nums</code>, return the length of the longest wiggle subsequence of <code>nums</code>.

&nbsp;
Example 1:

<pre>
Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).
</pre>

Example 2:

<pre>
Input: nums = [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] with differences (16, -7, 3, -3, 6, -8).
</pre>

Example 3:

<pre>
Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>
</ul>

&nbsp;
Follow up: Could you solve this in <code>O(n)</code> time?

wiggleMaxLength

Wiggle Subsequence

Rearrange Array Elements by Sign

rearrange-array-elements-by-sign

按符号重排数组

Greedy

Array

Dynamic Programming

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

<ul>
	<li>
	例如， <code>[1, 7, 4, 9, 2, 5]</code> 是一个 摆动序列 ，因为差值 <code>(6, -3, 5, -7, 3)</code> 是正负交替出现的。
	</li>
	<li>相反，<code>[1, 4, 7, 2, 5]</code> 和 <code>[1, 7, 4, 5, 5]</code> 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。</li>
</ul>

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 <code>nums</code> ，返回 <code>nums</code> 中作为 摆动序列 的 最长子序列的长度 。

 

示例 1：

<pre>
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
</pre>

示例 2：

<pre>
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
</pre>

示例 3：

<pre>
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
</pre>

 

提示：

<ul>
	<li><code>1 <= nums.length <= 1000</code></li>
	<li><code>0 <= nums[i] <= 1000</code></li>
</ul>

 

进阶：你能否用 <code>O(n)</code> 时间复杂度完成此题?