# LeetCode 376: Wiggle Subsequence

## Problem Restatement

We are given an integer array `nums`.

A wiggle sequence is a sequence where the differences between neighboring numbers strictly alternate between positive and negative.

For example:

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

The differences are:

```python
[6, -3, 5, -7, 3]
```

The signs alternate:

```text
positive, negative, positive, negative, positive
```

So this is a wiggle sequence.

We need to return the length of the longest wiggle subsequence.

A subsequence keeps the original order, but it may skip elements.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Length of the longest wiggle subsequence |
| Constraint | `1 <= nums.length <= 1000` |
| Constraint | `0 <= nums[i] <= 1000` |

Example function shape:

```python
def wiggleMaxLength(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 7, 4, 9, 2, 5]
```

The whole array already wiggles.

```text
1 -> 7 goes up
7 -> 4 goes down
4 -> 9 goes up
9 -> 2 goes down
2 -> 5 goes up
```

So the answer is:

```python
6
```

Example 2:

```python
nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
```

One longest wiggle subsequence is:

```python
[1, 17, 10, 13, 10, 16, 8]
```

Its differences are:

```python
[16, -7, 3, -3, 6, -8]
```

The signs alternate, so the answer is:

```python
7
```

Example 3:

```python
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
```

This array only increases.

We can choose any two different numbers to make a wiggle sequence of length `2`.

So the answer is:

```python
2
```

## First Thought: Dynamic Programming

A useful way to understand the problem is to keep two states.

For each position, we can ask:

| State | Meaning |
|---|---|
| `up` | Longest wiggle subsequence so far ending with an upward move |
| `down` | Longest wiggle subsequence so far ending with a downward move |

If the current number is greater than the previous number, we can extend a sequence that previously ended with a downward move.

So:

```python
up = down + 1
```

If the current number is smaller than the previous number, we can extend a sequence that previously ended with an upward move.

So:

```python
down = up + 1
```

Equal adjacent values do not help, because a wiggle sequence requires non-zero differences.

## Key Insight

We only care when the direction changes.

An increasing run like this:

```python
[1, 2, 3, 4, 5]
```

does not give many wiggles. It gives only one upward move.

For the longest wiggle subsequence, we only need the turning points: local lows and local highs.

For example:

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

Every step changes direction, so every number can be used.

But in:

```python
[1, 2, 3, 4, 5]
```

there is no direction change, so the best length is only `2`.

This leads to a greedy `O(n)` solution.

## Algorithm

Initialize:

```python
up = 1
down = 1
```

A single number is always a valid wiggle subsequence of length `1`.

Then scan from left to right.

For each adjacent pair `nums[i - 1]` and `nums[i]`:

If `nums[i] > nums[i - 1]`, the last move is upward, so update:

```python
up = down + 1
```

If `nums[i] < nums[i - 1]`, the last move is downward, so update:

```python
down = up + 1
```

If they are equal, do nothing.

At the end, return:

```python
max(up, down)
```

## Correctness

The variables `up` and `down` store the best wiggle length seen so far with two possible last-move directions.

When we see an upward difference, the current number can only extend a subsequence whose last move was downward. This creates a valid alternation, so `up = down + 1`.

When we see a downward difference, the current number can only extend a subsequence whose last move was upward. This creates a valid alternation, so `down = up + 1`.

When the difference is zero, adding the current number would create a zero difference, which is not allowed in a wiggle sequence. So the best lengths stay unchanged.

The greedy update is safe because within a monotonic run, only the endpoint matters. Replacing an earlier value in that run with a later, more extreme value cannot reduce the chance of forming the next opposite move. Therefore counting direction changes gives the same length as the best subsequence.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | We keep only two counters |

## Implementation

```python
class Solution:
    def wiggleMaxLength(self, nums: list[int]) -> int:
        up = 1
        down = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                up = down + 1
            elif nums[i] < nums[i - 1]:
                down = up + 1

        return max(up, down)
```

## Code Explanation

We start both states at `1`:

```python
up = 1
down = 1
```

A single element is valid by itself.

Then we compare each number with the previous number:

```python
for i in range(1, len(nums)):
```

If the current number is larger, the current step is an upward move:

```python
if nums[i] > nums[i - 1]:
    up = down + 1
```

This means the best upward-ending wiggle sequence comes from a previous downward-ending sequence.

If the current number is smaller, the current step is a downward move:

```python
elif nums[i] < nums[i - 1]:
    down = up + 1
```

Equal values are ignored because they produce a zero difference.

Finally:

```python
return max(up, down)
```

The longest wiggle subsequence may end with either an upward move or a downward move.

## Testing

```python
def test_solution():
    s = Solution()

    assert s.wiggleMaxLength([1, 7, 4, 9, 2, 5]) == 6
    assert s.wiggleMaxLength([1, 17, 5, 10, 13, 15, 10, 5, 16, 8]) == 7
    assert s.wiggleMaxLength([1, 2, 3, 4, 5, 6, 7, 8, 9]) == 2
    assert s.wiggleMaxLength([5]) == 1
    assert s.wiggleMaxLength([0, 0]) == 1
    assert s.wiggleMaxLength([3, 3, 3, 2, 5]) == 3
    assert s.wiggleMaxLength([1, 2, 2, 2, 1]) == 3

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 7, 4, 9, 2, 5]` | Already a full wiggle sequence |
| Long mixed example | Checks multiple turns |
| Strictly increasing array | Best answer is only `2` |
| Single element | Minimum input size |
| Equal values | Zero differences must be ignored |
| Duplicates before a turn | Confirms equal values do not reset state |
| Plateau in the middle | Confirms repeated equal values are skipped |