[Java] Longest wiggle subsequence

A wiggle sequence is a series of numbers where elements are strictly increasing or decreasing.

Given an array of numbers, find the longest wiggle subsequence. Example:

1,1 - longest is 1

1,2,3 - longest is 2

1,2,1 - longest is 3

The sequence can start going up or down, then all other elements must alternate between going down or up.

Now the FAST approach for dynamic programming might actually take you for a long tour before we reach the final solution.

If we start with a recursive top down approach, we find ourselves calling a function:

longestWiggleSubsequence(nums, currentElement, nextElement, direction)

as the sequence can start going either up or down and picking or not the first element. We can represent these combinations with a cache:

[current][next][direction]

Initially we would have:

• first,next,up = 1 //picked first element and going up to the next
• first,next,down = 1 //picked first element and going down to the next
• none,next,up = 0  //did not pick first element and going up to the next
• none,next,down = 0 //did not pick first element and going down to the next
  

However, we can also split this cache up in two separate caches:
  

up = [current][next]

down = [current][next]
 

where each pair of current,next elements indicate a position in the array and tracks the longest wiggle subsequence until then.
 

We notice that it's impossible to increase both subsequences at the same time as our choices for each pair are:

• curr < next: we can expand the down sequence only if the previous chosen element was > curr
• curr > next: we can expand the up sequence only if the previous chosen element was < curr
• curr == next: we can't improve any sequence
  

We could track the previous chosen element to implement this logic, but we again notice that the improvements only alternate between the two possible sequences:

• curr < next: we are improving from the best prev > curr (down) sequence
• curr > next: we are improving from the best prev < curr (up) sequence
  

as otherwise we would be improving on an invalid always increasing or decreasing sequence
 

We also notice we are looking at each pair current,next element once per sequence, so we don't need to track all combinations of elements, but only the best length for either sequence until a certain pair of elements. Our cache can become:

up = [best sequence so far going up at this element]

down = [best sequence so far going down at this element]
 

We finally notice as well that we need to look at each pair of elements once and more importantly, the best decision for either up or down until that point will be the best decision overall as the sequence is either increasing or decreasing but we do not require more knowledge than the last chosen elements (and the best until there).
 

We can therefore get rid of the arrays and use a simple variable.
 

This is similar to the problem where we are asked to find the longest increasing subsequence of elements in an array with the twist that we are interleaving two increasing and decreasing subsequences instead.

You can check my implementation of longestWiggleSubsequence on my Gist along with some tests in LongestWiggleSubsequenceJTests.