Solution: Longest Increasing Subsequence

Statement

The Longest Increasing Subsequence (LIS) is the longest subsequence from a given array in which the subsequence elements are sorted in a strictly increasing order. Given an integer array, nums, find the length of the LIS in this array.

Constraints:

• $1 \leq$ nums.length $\leq 985$
• $-10^4 \leq$ nums[i] $\leq 10^4$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

One solution that comes to mind to solve this problem is to use recursion. The idea is to generate all possible subsequences of the given array and check whether each subsequence is in a strictly increasing order. In the recursive approach, we consider two subproblems for each element in the array, i.e., including it in the subsequence or skipping it. We recursively solve these subproblems and return the maximum length of the subsequence.

However, this approach is computationally expensive, since it would require generating all possible subsequences, which would result in a time complexity of $O(2^n)$ ...