The starting idea for the algorithm is that we will scan the input from left to right, maintaining at any given time a representation of all the possible increasing subsequences that can be formed with the elements seen so far, such that the sub-sequences we track are ones that could contribute to the final solution. We will aggressively discard subsequences that can never influence the solution, and this will allow the algorithm to become efficient.

What subsequences can contribute to the solution? First, we note that if we have two subsequences of equal length, say,

3 -> 9 -> 11 -> 13

and

4 -> 6 -> 10 -> 15

Then, it only makes sense to track the one that has the smaller ending number (13 in this case). This is because if we ever extend either of these sequences with another number, even if we validly extended the second one, for example if we see the number 17 and do:

4 -> 6 -> 10 -> 15 -> 17,

we could have also extended the first one:

3 -> 9 -> 11 -> 13 -> 17

So, we lose nothing by forgetting all about the sequence ending with 15: as a general principle, the sequence ending with the smallest number can always replace the sequence ending with the larger number.

(However, the sequence ending with the smaller number might be able to be extended with numbers that the other can’t be extended with, such as 14 in this example, so the reverse argument does not work.)

As such, we now know it’s safe to maintain only one sequence per distinct sequence length: the one that ends in the smallest number.

Already, this paves the way to an [math]O(N^2)[/math] algorithm. As you process each new number in the input (let N be how many numbers are in the input), iterate through all sequences you are maintaining (at most N, one per distinct sequence length), and see to which sequences you can append that number. For each sequence where you can append the number, generate a new candidate sequence with the append. After generating the new candidate sequences, compare each one with the (at most one) other sequence you had of the same length, and keep only the one ending with the smaller number.

(To make sequences of the same length efficient to find, it’s best to have an array of pointers to sequences, with arr[k] representing the current best sequence of length k.)

Implemented sloppily, the above might be [math]O(N^3)[/math] due to copying of the sequences, but a sequence can be represented as simply a single number plus a pointer to the previous sequence it extends. Implemented this way, and because all the sequence comparisons look at only the last number in each sequence, we reach [math]O(N^2)[/math] time complexity (O(N) work, to look at the last number in each of up to N sequences, for each of the N numbers in the input).

To improve it further, we make another observation, which allows us to discard even more sequences!

We note that if we have two sequences of different length, and the longer one ends with a smaller or equal number than the shorter one, the shorter one can be discarded. If you have:

3 -> 9 -> 11 -> 12 -> 13

and

4 -> 6 -> 10 -> 15

You would never use the second one, by the same kind of reasoning as before. Importantly, this is true even when sequences end in the same number: 3 -> 9 -> 11 -> 12 -> 15 allows for 4 -> 6 -> 10 -> 15 to be discarded.

This means that now, since we will commit to discarding shorter sequences that exhibit the above pattern, we also have the guarantee that shorter sequences that we’re tracking end with smaller numbers than longer sequences.

That means that, if we have an array where arr[k] refers to the best sequence of length k, when we look at the ending numbers of the sequences in this array, we see something that looks like this (for some arbitrary example):

sequence ending num: unset, 2, 5, 10, 16, 26, unset, unset 
array index:             0, 1, 2,  3,  4,  5,     6,     7 

The important feature here is that the sequence end numbers are in ascending order.

Now, let’s say we read the next number from the input and it is 12. Which sequences can we append it to? Everything 10 and below. But, appending it to anything but 10 is useless, because all the sequences after the append will end in 12, and be discarded unless they are the longest sequence ending in 12. So, we need only append to the longest sequence to which we are able to append, 10 in this case.

After appending, we have a new candidate sequence ending in 12 whose length is 4. This sequence has a smaller or equal ending number than the previous best sequence of that length, because otherwise we would have extended that sequence. In this case, 12 is better than 16. We do the update and the new state becomes:

sequence ending num: unset, 2, 5, 10, 12, 26, unset, unset 
array index:             0, 1, 2,  3,  4,  5,     6,     7 

The array is really maintaining a pointer to the sequence object and not just the ending number so that you can recover the sequence afterwards.

The only remaining question is how, given the number 12, we can find the position of 10, in other words, the rightmost index whose value is less than the target value of 12. Remember the sequence ending numbers are in ascending order, so we can binary search. This allows each number of the input to be processed in O(log N), which results in a complexity of O(N log N).