LIS

Longest Increasing (Contiguous) Subsequence

The question of longest increasing subsequence, where "sequence" refers to numbers that are adjacent to one another, is one that connects to many other mathematical topics. See this book [1] for details.

Basic Problem Description

Definitions

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_n} denotes a group of permutations of order n, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma \in S_n} is a particular permutation of those n items, a subsequence of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma} is a sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma(i_1), \sigma(i_2), \dots, \sigma(i_k)} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1 \leq i_1 < i_2 < \dots < i_k \leq n}

An increasing subsequence satisfies the property Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma(i_1) < \sigma(i_2) < \dots < \sigma(i_k)}

A decreasing subsequence satisfies the property Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma(i_1) > \sigma(i_2) > \dots > \sigma(i_k)}

A monotone subsequence is either increasing or decreasing.

Now the quantity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L(\sigma)} can be used to refer to the maximum length of a particular permutation.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L(\sigma) = \max \left( 1 \leq k \leq n : \sigma \mbox{ has an increasing subsequence of length }k \right) }

Likewise, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D(\sigma)} refers to the max length of a decreasing subsequence.

Average Length

Stanislaw Ulam (of Manhattan Project fame, and the inventor of the Monte Carlo method) first mentioned the problem of determining the average value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L(\sigma)} over all permutations of order n, given by the expression:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle l_n = \dfrac{1}{n!} \sum_{\sigma \in S_n} L(\sigma) \qquad n = 1, 2, \dots }

The solution is complicated, but the asymptotic behavior of the above function is given by:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle l_n = 2 \sqrt{n} + c n^{\frac{1}{6}} + o(n^{\frac{1}{6}}) }

where c is -1.77108... and has a complicated definition given by a Painlevé differential equation of type 2.

Bounds on Average Length

Bounds can be placed on the average value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L(\sigma_n)} .

Lower bounds are given by:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E( l_n ) \geq \sqrt{n} }

An upper bound for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n \rightarrow \infty} can be given by

$\lim _{n\rightarrow \infty }\sup {\dfrac {l_{n}}{\sqrt {n}}}\leq e$

Hammsersley took a geometric approach and modeled the concept of a set as points in a box. An increasing subsequence consists of a line that is drawn through various points, that always has a positive slope.

Patience Sorting

Once you are given a permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma} , how do you actually compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L(\sigma)} ?

Consider the following algorithm: patience sorting

Technique was invented by ASC Ross in 1960, named by Colin Mallows.

Scan sequentially through a permutation of values in order, pile them into a linear array of stacks according to rules:

We are forming piles with cards.

Each card is placed at the top of a pile or creates a new right-most pile

To determine which pile a card goes onto, pick out all the piles whose current top number is greater than current card. Pick the left most pile and place the card on top of that pile.

If there are no piles whose top number is greater than the current card, start a new pile.

When patience sorting is applied to a permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma \in S_n} , the number of stacks at the end is equal to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L(\sigma)} .

Longest Increasing (Non-Contiguous) Subsequence

LIS for non-contiguous subsequences is a common dynamic programming problem. A description of an algorithm is given below.

Dynamic Program

Problem

Suppose we are given a sequence of n numbers, and we wish to design an algorithm to find the longest monotonically increasing subsequence within that sequence.

Here we take "sequence" to mean the numbers are not necessarily neighbors; "run" typically refers to a sequence of numbers that are adjacent to one another.

For example, if we take the sequence

S = {2, 4, 3, 5, 1, 7, 6, 9, 8}

then the longest increasing subsequence has length 5, and is given by:

LIS = {2, 3, 5, 6, 8}

Solution Procedure

To solve dynamic programming problems, apply these three steps:

1. Formulate answer as recurrence relation/recursive algorithm

2. Show that the number of parameters taken on by the recurrence is bounded by a polynomial

3. Specify the order of evaluation for the recurrence so that partial results that are needed are always available

Solution Algorithm

Longest increasing (non-contiguous) subsequence:

Step 1 - formulate answer as recurrence relation

We want to know the longest subsequence in the preceding numbers - if we are considering Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_n} , we want to know the longest increasing subsequence in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1, S_2, \dots, S_{n-1}}

However, we also want to know the length of the longest sequence that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_n} will extend

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L_j} be length of the longest subsequence that ends with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_j}

Base case: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L_0 = 0}

Now the quantity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L_j} is given by:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L_j = \max_{0 < i < j} L_j + 1 \qquad S_i < S_j }

This utilizes the fact that any subsequence ending at j must pick up where a prior sequence left off - at a prior position i < j. We also require that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_i < S_j} because otherwise we aren't continuing an increasing subsequence.

Then we just take the maximum of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L_i} , the longest subsequence ending at position i. Then add one to it, to extend the subsequence by one.

References

1. Romik, Dan. The Surprising Mathematics of Longest Increasing Subsequences. Manuscript, 20 August 2014. [2]