Understanding the bottom-up solution to the longest increasing subsequence problem

To find the longest increasing subsequence using a bottom-up dynamic programming approach, we fill a table iteratively starting from the smallest subproblems and progressing towards the final answer. As with any bottom-up solution, we process subproblems in an order that guarantees every result we need has already been computed and stored before we use it.

The bottom up solution

We create a 1D array lis of size n, where lis[i] stores the length of the longest increasing subsequence ending at index i in the array arr. We initialize every entry in lis to 1 since every single element is an increasing subsequence of length 1 on its own.

Since any sequence ending at index 0 will only have 1 item in it, the solution for it will always be 1, and so lis[0] = 1 serves as the base case for the problem.

We initialize a variable maxLength to 1 to keep track of the longest increasing subsequence found so far.