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)$, where $n$ is the number of elements in the nums array. This approach would not be feasible for large arrays.

Therefore, we need to devise an optimized approach that has a better time complexity to solve this problem.

Optimized approach using dynamic programming

Since the naive approach is costly in terms of time complexity, we can try to optimize the solution using dynamic programming. Let’s see if this problem satisfies both conditions of dynamic programming:

• Optimal substructure: If we have an array nums of size $n$, we can find the longest increasing subsequence of each subarray of size $n-1$ and then select the maximum out of these solutions. Since solving the subproblems of size $n-1$ helps us solve the problem of size $n$, this problem has the optimal substructure property.

• Overlapping subproblems: The following illustration highlights the overlapping subproblems. There are two recursive calls for $(2, 1)$ (highlighted in blue), four calls for $(3, 2)$ (highlighted in purple), and so on. The function is computing certain results over and over again, which is inefficient. Therefore, this problem has the overlapping subproblems property.

Given this analysis, we can feel confident that we can optimize our solution using dynamic programming.