Wiggle Subsequence

Problem Statement

In the context of arrays, a wiggle sequence is defined as a sequence where the differences between successive numbers in the sequence strictly alternate between positive and negative. The initial difference in the sequence could either be positive or negative. Notably, a single element sequence, as well as any two-element sequence with distinct numbers, automatically qualify as wiggle sequences.

To elaborate, consider the sequence [1, 7, 4, 9, 2, 5] which qualifies as a wiggle sequence. This is deduced from the difference between successive elements: (6, -3, 5, -7, 3), which alternates between positive and negative. Conversely, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] do not meet the criteria for a wiggle sequence. The former sequence has its first two differences as positive and hence does not alternate, while the latter has a difference of zero which is neither positive nor negative.

A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Given an integer array nums, the task is to determine the length of the longest wiggle subsequence within nums.

Examples

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

Approach and Intuition

A nuanced understanding of the problem can be attributed to the observation of changes in the trend of the sequence. When considering how to determine the longest wiggle subsequence, a straightforward method involves:

1. Define a default sequence starting with the first two distinct elements which establish the initial trend (either increasing or decreasing).
2. Traverse through the array and compare each element to the previous one to detect a change in the gradient (from increasing to decreasing or vice versa).
3. Whenever a change in the trend is observed, include that element in the wiggle subsequence. This captures the point where the sequence wiggles.
4. Continue this until all elements are assessed.

This simpler greedy approach leverages capturing each point of transition to construct the longest possible wiggle sequence.

Understanding Through Examples:

• Example 1: For input nums = [1,7,4,9,2,5], we observe that the entire sequence forms a wiggle pattern. Hence, the longest wiggle subsequence includes all elements, so the output is 6.

• Example 2: For input nums = [1,17,5,10,13,15,10,5,16,8], a possible longest wiggle subsequence could be [1, 17, 5, 10, 13, 10, 16, 8]. This subsequence has consistent alternation between rise and fall, giving a length of 7.

• Example 3: Given nums = [1,2,3,4,5,6,7,8,9], this array is consistently increasing, thus only two elements can be used to form a valid wiggle subsequence (e.g., [1, 2] or any two consecutive numbers), resulting in the maximum length being 2.

By following these intuitions and steps, we can efficiently determine the length of the longest wiggle subsequence without needing any advanced data structures, utilizing basic array manipulations and conditional assessments.

Solutions

public class Solution {
    public int getMaxWiggleLength(int[] sequence) {
        if (sequence.length < 2)
            return sequence.length;
        int lastDifference = sequence[1] - sequence[0];
        int length = lastDifference != 0 ? 2 : 1;
        for (int index = 2; index < sequence.length; index++) {
            int currentDiff = sequence[index] - sequence[index - 1];
            if ((currentDiff > 0 && lastDifference <= 0) || (currentDiff < 0 && lastDifference >= 0)) {
                length++;
                lastDifference = currentDiff;
            }
        }
        return length;
    }
}