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 $S_{n}$ denotes a group of permutations of order n, and $\sigma \in S_{n}$ is a particular permutation of those n items, a subsequence of $\sigma$ is a sequence $\sigma (i_{1}),\sigma (i_{2}),\dots ,\sigma (i_{k})$, where $1\leq i_{1}<i_{2}<\dots <i_{k}\leq n$

An increasing subsequence satisfies the property $\sigma (i_{1})<\sigma (i_{2})<\dots <\sigma (i_{k})$

A decreasing subsequence satisfies the property $\sigma (i_{1})>\sigma (i_{2})>\dots >\sigma (i_{k})$

A monotone subsequence is either increasing or decreasing.

Now the quantity $L(\sigma )$ can be used to refer to the maximum length of a particular permutation.

$L(\sigma )=\max \left(1\leq k\leq n:\sigma {\mbox{ has an increasing subsequence of length }}k\right)$

Likewise, $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 $L(\sigma )$ over all permutations of order n, given by the expression:

$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:

$l_{n}=2{\sqrt {n}}+cn^{\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 $L(\sigma _{n})$.

Lower bounds are given by:

$E(l_{n})\geq {\sqrt {n}}$

An upper bound for $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 $\sigma$, how do you actually compute $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 $\sigma \in S_{n}$, the number of stacks at the end is equal to $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 $S_{n}$, we want to know the longest increasing subsequence in $S_{1},S_{2},\dots ,S_{n-1}$

However, we also want to know the length of the longest sequence that $S_{n}$ will extend

Let $L_{j}$ be length of the longest subsequence that ends with $S_{j}$

Base case: $L_{0}=0$

Now the quantity $L_{j}$ is given by:

$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 $S_{i}<S_{j}$ because otherwise we aren't continuing an increasing subsequence.

Then we just take the maximum of $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]