How to Solve LIS

In this tutorial, I'll refer to the longest increasing subsequence as LIS. Let's first explore a simple recursive technique that can find the LIS for an array. We'll use the following notation to explain:

Suppose we have a function LIS(arr, n). Let this function reflect the length of the longest increasing sub-sequence that has arr[n] as "its last element".

We'll build on this function shortly. With this, let's look at the examples below. Here, all the subsequence indices start from zero. We're just exploring some patterns for now:

1// in the below example, we're looking for arr[0], which is 1
2LIS({1,3,4,0}, 0) = 1        // the solution is the simple subsequence {1}
3
4// continuing the pattern
5// here we're looking for a subsequence ending in arr[1]
6LIS({1,3,4,0}, 1) = 2        // the subsequence {1,3} w/ length 2
7// further continuing..
8LIS({1,3,4,0}, 2) = 3        // the subsequence {1,3,4} w/ length 3
9LIS({1,3,4,0}, 3) = 1        // the subsequence {0} as it has to include arr[3]

Some observations emerge as we go through this exercise: as the subsequence has to end in arr[n], it can only include elements that satisfy two conditions:

1. The elements need to be at an index smaller than n.
2. The elements themselves must be smaller than arr[n] to fit the "increasing subsequence" condition.

We can thus derive the following rule from our observations:

1LIS(arr, n) = 1 + max( LIS(arr, j) ) max computed over all j, 0<=j<n and arr[j]<arr[n]

We can translate this into plain English: if we can find LIS(arr, n) (the LIS with arr[n] as its last element) for all indices of the array, then the longest increasing subsequence for the entire array LISMax(arr) would be the maximum of all the LIS(arr, n), computed for all valid indices n:

1LISMax(arr) = max( LIS(arr, n) ) max computed for all valid indices n of the array