# Wiggle Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/wiggle-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/wiggle-subsequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Electronic Arts](https://scaleengineer.com/companies/electronic-arts)
---
## Problem
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.

* 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.
* 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.

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 `nums`, return _the length of the longest **wiggle subsequence** of_ `nums`.

**Example 1:**

**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).

**Example 2:**

**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).

**Example 3:**

**Input:** nums = [1,2,3,4,5,6,7,8,9]
**Output:** 2

**Constraints:**

* `1 <= nums.length <= 1000`
* `0 <= nums[i] <= 1000`

**Follow up:** Could you solve this in `O(n)` time?

# Approaches
## Dynamic Programming
This problem has optimal substructure and overlapping subproblems, making it a good candidate for dynamic programming. We can define the state based on the length of the wiggle subsequence ending at each index. However, to correctly build the sequence, we also need to know the direction of the last wiggle (up or down). Therefore, we use two DP arrays: one for subsequences ending with an upward wiggle (`up`) and one for those ending with a downward wiggle (`down`).
**Time:** O(n^2), where n is the number of elements in the input array. The nested loops dominate the runtime. · **Space:** O(n), where n is the number of elements in the input array. We use two arrays, `up` and `down`, of size n.
**Pros:** It is a standard and intuitive dynamic programming solution.; Guaranteed to find the correct optimal solution.
**Cons:** The time complexity is quadratic, which might be too slow for very large input arrays.; Requires extra space proportional to the input size.
### Explanation
We define `up[i]` as the length of the longest wiggle subsequence of `nums[0...i]` ending at `nums[i]`, where the last difference is positive. Similarly, `down[i]` is the length of the longest wiggle subsequence ending at `nums[i]` where the last difference is negative.

To compute `up[i]`, we look at all previous elements `nums[j]` (where `j < i`). If `nums[i] > nums[j]`, it means we can append `nums[i]` to a wiggle subsequence that ended at `nums[j]` with a downward wiggle. The new length would be `down[j] + 1`. We take the maximum over all possible `j`.

`up[i] = 1 + max(down[j])` for all `j < i` where `nums[i] > nums[j]`.

Similarly, for `down[i]`, we look for `nums[j]` where `nums[i] < nums[j]`. We can append `nums[i]` to a wiggle subsequence that ended at `nums[j]` with an upward wiggle. The new length would be `up[j] + 1`.

`down[i] = 1 + max(up[j])` for all `j < i` where `nums[i] < nums[j]`.

The base case is that any element by itself is a wiggle subsequence of length 1, so `up[i]` and `down[i]` are initialized to 1. The final answer is the maximum value in either `up` or `down` arrays after filling them.

```java
import java.util.Arrays;

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }
        int n = nums.length;
        int[] up = new int[n];
        int[] down = new int[n];
        Arrays.fill(up, 1);
        Arrays.fill(down, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = Math.max(up[i], down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = Math.max(down[i], up[j] + 1);
                }
            }
        }

        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            maxLength = Math.max(maxLength, Math.max(up[i], down[i]));
        }
        return maxLength;
    }
}
```
### Algorithm
- Create two integer arrays, `up` and `down`, of the same size as the input array `nums`.
- `up[i]` will store the length of the longest wiggle subsequence ending at index `i` with a positive difference (an "up" wiggle).
- `down[i]` will store the length of the longest wiggle subsequence ending at index `i` with a negative difference (a "down" wiggle).
- Initialize all elements of `up` and `down` to 1, as any single element is a wiggle subsequence of length 1.
- Iterate through the array `nums` with an outer loop from `i = 1` to `n-1`.
- Inside, have an inner loop from `j = 0` to `i-1`.
- If `nums[i] > nums[j]`, it means we can potentially extend a "down" wiggle ending at `j`. Update `up[i] = max(up[i], down[j] + 1)`.
- If `nums[i] < nums[j]`, it means we can potentially extend an "up" wiggle ending at `j`. Update `down[i] = max(down[i], up[j] + 1)`.
- After the loops complete, the length of the longest wiggle subsequence is the maximum value found in either the `up` or `down` array.
- Handle the edge case of an empty or single-element array separately; the length is simply the number of elements.

## Greedy Approach
A more efficient approach is to use a greedy strategy. The core idea is that we only need to track the length of the longest wiggle subsequence ending in an upward movement and one ending in a downward movement. When we iterate through the array, we can extend one of these sequences based on the current element's relation to the previous one. This avoids the need for the inner loop of the DP approach, reducing the complexity significantly.
**Time:** O(n), where n is the number of elements in the input array. We perform a single pass through the array. · **Space:** O(1). We only use a few constant extra variables (`up`, `down`).
**Pros:** Extremely efficient with linear time complexity.; Uses constant extra space, making it optimal in terms of memory.
**Cons:** The greedy logic can be less obvious to prove correct compared to the straightforward DP formulation.
### Explanation
This approach can be seen as a space-optimized version of the O(n^2) DP solution. Instead of two arrays, we only need two variables, `up` and `down`, to store the lengths of the longest wiggle subsequences ending with a positive and negative difference, respectively.

We initialize `up = 1` and `down = 1`, representing the subsequence formed by the first element. Then, we iterate from the second element. For each element `nums[i]`, we consider the difference `nums[i] - nums[i-1]`:

- If `nums[i] > nums[i-1]` (an up-slope): We can form a new, longer subsequence ending with an up-slope by appending `nums[i]` to any previous subsequence that ended with a down-slope. The longest such new sequence will have length `down + 1`. We update `up` to this new length. The `down` length doesn't change, as we are on an up-slope.
- If `nums[i] < nums[i-1]` (a down-slope): Similarly, we can extend a previous up-slope sequence. We update `down` to `up + 1`.
- If `nums[i] == nums[i-1]`: The element is a duplicate of the previous one. It cannot extend a wiggle sequence, so we ignore it and `up` and `down` remain the same.

This works because any consecutive run of increasing or decreasing numbers can be represented by just its start and end points in a wiggle subsequence. The greedy choice of always extending the sequence with the very next peak or valley proves to be optimal.

```java
public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }
        // up: length of longest wiggle subsequence ending with a positive difference
        // down: length of longest wiggle subsequence ending with a negative difference
        int up = 1;
        int 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);
    }
}
```
### Algorithm
- Handle the base case: if the array has fewer than 2 elements, return its length.
- Initialize two variables, `up` and `down`, to 1. `up` will track the length of the longest wiggle subsequence ending with an upward wiggle, and `down` will track the length for a downward wiggle.
- Iterate through the array from the second element (`i = 1` to `n-1`).
- At each element `nums[i]`, compare it with the previous element `nums[i-1]`.
- If `nums[i] > nums[i-1]`, we have an "up" slope. This can extend a subsequence that ended in a "down" slope. So, we update `up = down + 1`. The `down` length remains unchanged because we can't extend a down-slope sequence with an up-slope move from the immediately preceding element.
- If `nums[i] < nums[i-1]`, we have a "down" slope. This can extend a subsequence that ended in an "up" slope. So, we update `down = up + 1`. The `up` length remains unchanged.
- If `nums[i] == nums[i-1]`, the sequence is flat, which doesn't contribute to a wiggle. We do nothing and both `up` and `down` remain unchanged.
- After the loop, the result is the maximum of the final `up` and `down` values.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int wiggleMaxLength(vector<int> &nums) {
    int up = 1, down = 1;
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] > nums[i - 1]) {
        up = max(up, down + 1);
      } else if (nums[i] < nums[i - 1]) {
        down = max(down, up + 1);
      }
    }
    return max(up, down);
  }
};

```

### Python

```python
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int: up = down = 1 for i in range(1, len(nums)): if nums[i] > nums[i - 1]: up = max(up, down + 1) elif nums[i] < nums[i - 1]: down = max(down, up + 1) return max(up, down)  # class Solution ( object ): def wiggleMaxLength ( self , nums ): """ :type nums: List[int] :rtype: int """ if not nums : return 0 up = 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 )

```