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.

The lis function

The function lis takes as input an index i, a reference to the array arr, and a reference to the memoization array memo. The function returns the length of the longest increasing subsequence ending at index i.

Create a function lis to return the length of longest increasing subsequence at index i.

Why does lis(i) only return the LIS ending at index i, instead of the LIS of the whole array?

Because the LIS can end at any index, not necessarily the last one. For example, in [1, 2, 3, 0], the LIS ends at index 2, not at index 3. We make lis answer a local question for each index, then take the maximum across all indices in the calling function. Without anchoring the subproblem to a specific ending index, we wouldn't have a clean recurrence.

The memo array has n entries and is initialized with -1 in the calling function, where -1 indicates that the state has not yet been computed. Any non-negative value represents the computed length of the longest increasing subsequence ending at that index.