Understanding the longest increasing subsequence problem

In many software systems, programs must process sequences of data and identify useful patterns within them, for example, detecting periods when a metric steadily improves, analyzing trends in stock prices, or tracking the progression of user activity over time. While this may sound simple, the challenge lies in the sheer number of possible subsequences that can be formed from a given sequence, making it surprisingly difficult to determine the optimal one efficiently.

This type of challenge appears frequently in computer science, and a classic formulation of it is the Longest Increasing Subsequence (LIS) problem, where we are given a sequence of numbers, and we need to determine the longest subsequence in which each element is strictly greater than the one before it.

In this lesson, we will learn about the longest increasing subsequence problem and how it can be solved efficiently using a dynamic programming solution.

The longest increasing subsequence problem

Consider we are given an array of integers arr of length n. A subsequence in this array is defined as a sequence of integers from the array that appear in the same order as in the array.

We need to find the length of the longest subsequence such that all elements in the subsequence are in strictly increasing order.