Understanding the problem

Many of the problems we face in everyday life and in computing involve making a series of decisions, combining options, or finding the best outcome among many possibilities. When the choices are few, these problems are easy, often trivial. We can solve them in our heads or by scribbling a few options on paper. But as the input grows, the number of possible combinations explodes, and what was once a simple task becomes impossibly slow. Let's look at several real-world situations where small instances feel effortless but larger instances quickly become unmanageable.

Finding the longest upward streak

Suppose you have the daily closing prices of a stock over a week: [30, 45, 20, 50, 35, 60]. You want to pick out the longest sequence of days, in order but not necessarily consecutive, on which the price was strictly higher each time you picked. Scanning by eye, it is easy to spot 30, 45, 50, 60 are the four days on which the price kept climbing, even though other days in between saw it dip. With only a handful of numbers, it is easy to find the longest such run without much trouble.