# 376. Wiggle Subsequence

Source link: https://leetcode.com/problems/wiggle-subsequence/

## Design

[1,17,5,10,13,15,10,5,16,8] → 7 ([1,17,10,13,10,16,8])

up: 1 2 2 4 4 4 4 4 6 6

down: 1 1 3 3 3 3 5 5 5 7

### Method I

- Initialize two arrays
*up*and*down*, the array*up*is for recording the length of the subsequence that wiggles up, and the array*down*is for recording the length of the subsequence that wiggles down. - Assign the first element of both arrays with 1.
- Travel through the array
*nums*, if nums[i] > nums[i -1], means that the previous element must be a down position, then up[i] = down[i - 1] + 1, down[i] keeps the same value before. If nums[i] < nums[i - 1], means that the previous element must be an up position, then down[i] = up[i - 1] + 1, up[i] keeps the same value as before. If nums[i] = nums[i - 1], then both up[i] and down[i] keeps the same value as before. - Return the max value between last values of both
*up*and*down*.

### Method II

This approach only need two pointers *up* and *down* to record the lengths of sequences that wiggle up and down, which could effectively reduce the space complexity.

## Implementation

### Method I

```
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length == 0 || nums == null) return 0;
int[] up = new int[nums.length];
int[] down = new int[nums.length];
up[0] = 1;
down[0] = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
up[i] = down[i - 1] + 1;
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {
down[i] = up[i - 1] + 1;
up[i] = up[i - 1];
} else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return Math.max(up[nums.length - 1], down[nums.length - 1]);
}
}
```

### Method II

```
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length == 0 || nums == null) return 0;
int up = 1, down = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}
```

## Complexity Analysis

### Method I

Time: $O(n)$

Space: $O(n)$

### Method II

Time: $O(n)$

Space: $O(1)$