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.