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.

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.

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

Three dynamic programming 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

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

Step 2 - To formulate the recurrence relation:

• Let L_i be length of the longest subsequence that ends with S_i
• Base case: L_0 = 0
• L_i given by:

$ L_i = \max_{0 < j < i} L_j + 1 \qquad S_j < S_i $

Skiena does not explain this very clearly, in particular the case where i = 1, so... not sure what's going on there.