Introduction

The Longest Increasing Subsequence (LIS) problem is a fundamental combinatorial problem in computer science and mathematics. Given a sequence of numbers, the task is to identify the longest subsequence in which the elements are in increasing order. This problem has applications in various fields such as bioinformatics, pattern recognition, and data compression.

Definition

Formally, given a sequence of integers $S = {s_1, s_2, \ldots, s_n}$, the objective is to find a subsequence $S' = {s'_{i_1}, s'_{i_2}, \ldots, s'_{i_k}}$ such that: • $s'_{i_1} < s'_{i_2} < \ldots < s'_{i_k}$ • The length of $S'$ is the maximum among all possible increasing subsequences of $S$.

Example

Consider the sequence $S = [10, 22, 9, 33, 21, 50, 41, 60, 80]$. One possible longest increasing subsequence is $[10, 22, 33, 50, 60, 80]$, which has a length of 6.

Algorithms

Dynamic Programming Approach

The most straightforward approach to solving the LIS problem is through dynamic programming. The idea is to construct an array `dp[]` where `dp[i]` represents the length of the longest increasing subsequence ending at index `i`.

Steps:

1. Initialize `dp[]` with all entries as 1, since every element is an increasing subsequence of length 1 by itself.
2. For each element at index `i`, check all previous elements `j` (where $0 \le j < i$) and update `dp[i]` if a longer increasing subsequence ending at `i` is found: $$dp[i] = \max(dp[i], dp[j] + 1) \text{ if } S[i] > S[j]$$
3. The result is the maximum value in `dp[]`.

Complexity: The time complexity of this approach is $O(n^2)$ where $n$ is the length of the sequence.

Patience Sorting and Binary Search

A more efficient solution can be developed using a combination of patience sorting and binary search. This method reduces the time complexity to $O(n \log n)$.

Steps:

1. Initialize an empty list `tail`.
2. Iterate over each element in the sequence: • Use binary search (in conjunction with the `bisect` module in Python) to find the position where the current element can replace a larger element in `tail`. • If the element is larger than all elements in `tail`, append it. • Otherwise, replace the found position in `tail` with the current element.
3. The length of `tail` at the end of iteration is the length of the LIS.

Why it Works: The `tail` array maintains potential candidates for the LIS, often hinting at where the current subsequence could continue or evolve.

Example Implementation

Here is an example of the patience sorting algorithm with binary search in Python: