Longest Increasing Subsequence

The problem is to find the longest increasing subsequence of an array.

We keep a list of subsequences. On iterating from left to right, we see if an element can be added to an existing subsequence. If not, we see if it can be added to a partial subsequence and we add the new subsequence to the list.

In the above example

• Initially from three elements we have subsequences [2, 6, 8]
• Adding 3, we get [2, 6, 8] and [2, 3]
• Adding 4, we get [2, 6, 8] and [2, 3, 4]
  • There’s no point in creating the subsequence [2, 4]
• Adding 7, we get [2, 6, 8], [2, 3, 4, 7] and [2, 6, 7]
• Adding 5, we get [2, 6, 8], [2, 3, 4, 7], [2, 6, 7] and [2, 3, 4, 5]

Instead of maintaining different lists, we can do this:

• On adding 3 to [2, 6, 8] we just find the number just greater than 3 in it and put 3 in its replace. So, it becomes [2, 3, 8].
• On adding 4, we get [2, 3, 4]

Doing so on, we are just maintaining one list. [2, 3, 8] is a combination of [2, 3] and [2, 6, 8]. Basically, keeping 6 there serves no purpose. A number greater than 8 will add to the subsequence and a number smaller than 8 but larger than 3 will add to [2, 3].

Keeping the minimum, we ensure that we always keep the better list. When we have [2, 3, 4], it is a combination of [2, 3, 4] and [2, 6, 8]. However, 4 < 8 and the former is kept as there’s more potential there, in simple words.