Read the latest issue of Notices  Read the latest issue of Bulletin  Shop in the AMS Bookstore  My Account | Cart  
 
American Mathematical Society   

>> 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.

 

 

Read on!

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

 

From the Feature Column editor's desk 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

View the full archive

Visit the rest of the site Visit the rest of the site
  Related Links
Search the site Search the AMS website:

Google
Web AMS Website