LIS

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.