Largest wiggle sequence

Problem: A sequence of numbers is called a wiggle sequence if 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 or no element is trivially a wiggle sequence.

For example, [1,5,4,7,2,3] is a wiggle sequence because the differences (4,-1,3,-5,1) are alternately positive and negative.

Given an array of integers, return the length of the longest wiggle subsequence.

Example:

Input: [1,5,4,7,2,3]
Output: 6
Explanation: The entire array is a wiggle sequence.

Input: [5,5]
Output: 1
Explanation: The longest wiggle sequence is [5].

Approach: We can use DP here. We can have two 1D tables say IncreasingSequence and DecreasingSequence. 

• IncreasingSequence[i] will tell the length of largest wiggle sequence where last element of sequence is array[i] and is greater than the second last element of sequence.
• DecreasingSequence[i] will tell the length of largest wiggle sequence where last element of sequence is array[i] and is less than the second last element of sequence.

Let's see how we can fill these tables. At any index 'i', we can have these three conditions:

1. arr[i] > arr[i - 1]: That means I can add arr[i] into wiggle sequence only if last element of sequence is arr[i - 1] and second last element of sequence is greater than arr[i - 1]. Right. That means I can say IncreasingSequence[i] = DecreasingSequence[i - 1] + 1 but there will be no change in DecreasingSequence, that means DecreasingSequence[i] = DecreasingSequence[i - 1].
2. arr[i] <  arr[i - 1]: That means I can add arr[i] into wiggle sequence only if last element of sequence is arr[i - 1] and second last element of sequence is less than arr[i - 1]. That means I can say DecreasingSequence[i] = IncreasingSequence[i - 1] + 1 but there will be no change in IncreasingSequence, that means IncreasingSequence[i] = IncreasingSequence[i - 1].
3. arr[i] = arr[i - 1]: No changes need to be made as both are equal, I don't have to add arr[i] into sequence. That means IncreasingSequence[i] = IncreasingSequence[i - 1] and DecreasingSequence[i] = DecreasingSequence[i - 1]

Obviously Max(IncreasingSequence[n-1], DecreasingSequence[n-1]) will be our answer. With this we can solve the problem in linear time. Can we still do better?

In terms of time we can't do any better as we have to touch every element of the array but if you see we are taking O(n) extra space. Let's optimize the space.

If you at any index 'i',  we are always using IncreasingSequence[i-1] and DecreasingSequence[i-1] to calculate IncreasingSequence[i] and DecreasingSequence[i]. That means if we can store previous maximum length of increasing sequence and decreasing sequence in variables, we can get rid of these tables.

That's all!

Implementation in C#:

        public int WiggleMaxLength(int[] nums)

        {

            if (nums?.Length <= 1)

            {

                return (int)nums?.Length;

            }

            int increasingSeqLen = 1, decreasingSeqLen = 1;

            for (int i = 1; i < nums.Length; ++i)

            {

                if (nums[i] > nums[i-1])

                {

                    increasingSeqLen = decreasingSeqLen + 1;

                }

                else if (nums[i] < nums[i-1])

                {

                    decreasingSeqLen = increasingSeqLen + 1;

                }

            }

            return Math.Max(increasingSeqLen, decreasingSeqLen);

        }

Complexity: O(n)