Understanding the top down solution to the longest increasing subsequence problem

To find the longest increasing subsequence using a top-down dynamic programming approach, we express the recurrence relation through recursive function calls and avoid redundant computation by caching results in a memoization array.

The top down solution

As with any top-down solution, there is a recursive function that solves subproblems and a calling function that initializes the required data structures and triggers the computation. For the longest increasing subsequence, we define a single recursive function lis and a calling function that iterates over all indices to find the global maximum.