376. Wiggle Subsequence Medium

1/**
2 * [376] Wiggle Subsequence
3 *
4 * 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.
5 * 
6 * 	For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
7 * 	In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] 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.
8 * 
9 * A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
10 * Given an integer array nums, return the length of the longest wiggle subsequence of nums.
11 *  
12 * Example 1:
13 * 
14 * Input: nums = [1,7,4,9,2,5]
15 * Output: 6
16 * Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).
17 * 
18 * Example 2:
19 * 
20 * Input: nums = [1,17,5,10,13,15,10,5,16,8]
21 * Output: 7
22 * Explanation: There are several subsequences that achieve this length.
23 * One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).
24 * 
25 * Example 3:
26 * 
27 * Input: nums = [1,2,3,4,5,6,7,8,9]
28 * Output: 2
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= nums.length <= 1000
34 * 	0 <= nums[i] <= 1000
35 * 
36 *  
37 * Follow up: Could you solve this in O(n) time?
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/wiggle-subsequence/
43// discuss: https://leetcode.com/problems/wiggle-subsequence/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn wiggle_max_length(nums: Vec<i32>) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_376() {
61    }
62}
63