[Java] Longest increasing subsequence

Given an array of integers, find the longest increasing subsequence. If there are more, find any.

I got to this while solving a different problem, which asked to determine whether an array of integers contained a triple of elements such that i < j < k and each element appeared before the next in the array.

Turns out for that problem you can go from a O(N^3) to O(N) time solution using constant space.

The idea there is to walk the array from left to right tracking the smallest and second smallest values so far. Whenever an element is bigger than both, you have a triple.

When updating smallest and second smallest, perform the checks:

current > i && current < j: update j

current < i: update i

current > j && j > i: triple exists

Although this method works even for sequences such as 1,5,0,6 it does not allow to determine which elements compose the triple as the property it relies on, only involves the knowledge that at some point in time we had two elements i, j such that i < j and the current element is bigger than j, therefore it must also be bigger than i.

But if you run the algorithm on the sample input, you will notice the final values are i = 0, j = 5 which is NOT a valid subsequence.

So I thought about how would you find the actual triple, which means how do we find an increasing subsequence of length 3, and which elements compose it.

The patience sorting algorithm is a good starting point as it is a sort algorithm that can be modified to track the longest increasing subsequence.

Using a similar idea, we get to the final algorithm using two auxiliary arrays:

• predecessor[i] = INDEX of PREVIOUS element part of the longest subsequence ending at element in position i
• minIndex[i] = INDEX of the SMALLEST LAST element of the latest found longest subsequence of length i. Since indices here are lengths, we have N+1 elements in this array and first index (length 0) has value -1 as we simply do not pick any element to form a subsequence of length 0

Then we scan the input array left to right and using the Fredman-Knuth variant we perform a first check: 

if the current element can improve on the longest subsequence so far, add it to the sequence and continue

Otherwise we execute the standard algorithm: if the current element cannot improve on the longest subsequence so far maybe it can improve some other previous subsequence, start a new subsequence or offer a better choice for the SMALLEST LAST element of the current subsequence, we need to find the longest of those we can be used to improve upon.

minIndex[i] tracks the INDEX of the SMALLEST LAST element for a subsequence of length i, this means:

minIndex[0] < minIndex[1] < ... < minIndex[i]

which also means the elements pointed at by those indices are sorted in increasing order
 

We search for the longest subsequence we can improve upon using this element which means searching for an UPPER bound, that is the SMALLEST LAST element of a longest subsequence that is bigger than us in order to replace it and therefore allow more possibilities to expand on that subsequence in the future
 

Example:

1,2,5,3,4,5

when we get to 3 the longest subsequence is 1,2,5 and we can't improve it by adding 3

however, by replacing 5 with 3, we allow more values in the next part of the array to join the longest subsequence until there
 

Other example:

1,2,10,11,3,4,5,6

when we get to 3, we can't improve 1,2,10,11 and we also cannot replace 11 as the previous element is 10

we could however use 3 instead of the portion 10,11 if at any point other elements bigger than 3 but smaller than 10 appear, leading to a longer subsequence.

We track that by setting the index of LAST element of a sequence of length 3 to be 3 instead of 10 as it currently was. The longest subsequence is still 4

when 4 arrives, we repeat the process but the longest subsequence is still of length 4 however the sequence 1,2,10,11 is now completely replaced by 1,2,3,4

when 5 arrives, we realize this approach paid off as we can now expand the current subsequence by adding it.

At the end, we have the latest found longest increasing subsequence tracked in our arrays, and need to reconstruct it. The values are however stored in reverse order from the last to the first, so we need to walk our arrays from the right.

The element in position maxLength of minIndex array will be the LAST element of the longest subsequence. By looking at the predecessor array, we can find all previous elements in this sequence.

The total space usage is O(N) and time is O(N log N), however with the Fredman-Knuth variant, we actually have O(N log N - N log log N + N) time.

You can check my implementation of longestIncreasingSubsequence and increasingSubtriple on my Gist along with some tests in LongestIncreasingSubsequenceJTests and IncreasingSubtripleJTests.