This Month's Feature Column

How Much Longer Can This Go On?

How can we systematically find the longest increasing subsequence?

Introduction

Suppose given a sequence of distinct numbers, and we ask, what is the length of the longest increasing subsequence?

For example, I give you

2, 5, 1, 4, 7, 6, 3.

Trial and error give you almost immediately several subsequences of length 3, such as 2, 5, 7. In fact, it's easy to write down all those of length 3:

2, 5, 7
2, 5, 6
2, 4, 7
2, 4, 6
1, 4, 7
1, 4, 6

So the question quickly becomes, are there any of length 4? Well, any subsequence of length 4 would have to extend one of length 3, so you can just look at all of length 3 and see if any can be extended. The answer is, no.

So if you think only of short sequences, this will seem easy to answer. I'll demonstrate a graphical method that will help you do the necessary mental calculation quickly. But suppose I give you a sequence of 100 numbers

41, 93, 31, 73, 98, 29, 12, 54, 24, 0, 52, 78, 87, 55, 25, 81, 76, 91, 51, 7, 39, 92, 65, 40, 45, 5, 1, 20, 84, 99, 27, 32, 13, 8, 2, 61, 19, 9, 74, 60, 66, 79, 47, 86, 30, 3, 85, 42, 89, 43, 70, 17, 6, 63, 28, 11, 34, 75, 22, 64, 59, 16, 48, 15, 90, 80, 69, 67, 35, 72, 50, 14, 33, 53, 10, 38, 94, 18, 58, 46, 49, 88, 68, 21, 62, 44, 97, 82, 37, 83, 95, 4, 56, 57, 77, 23, 96, 26, 36, 71 ?

Answering this question will involve a few digressions, and will have connections to many parts of mathematics. In the first part of this column, I'll explain how to solve the problem posed here, very little more and no less. In the second, I'll say something about extensions into other matters.

Bill Casselman
University of British Columbia, Vancouver, Canada
cass at math.ubc.ca

From the editor's desk

Welcome!

These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Mathematics is a fast growing and evolving subject. The domain of ways that mathematics is being applied is growing by leaps and bounds. Examples include CT scans, audio CD's, face recognition systems, and cell phone technology. Our goal is to share our excitement about these developments with you.
More . . .

Feature Columns at a Glance

May: Simon Newcomb and "Natural Numbers" (Benford's Law)
April: Mathematics and Climate
March: No Static at All: Frequency modulation and music synthesis
February: The Mathematics of Rainbows
January: People Making a Difference
December: Trees, Teeth, and Time: The mathematics of clock making
November: From Bézier to Bernstein
October: Inside-out Frieze Symmetries in Ancient Peruvian Weavings
September: Gray Codes
August: Percolation: Slipping through the Cracks

View the full archive

Visit the rest of the site