The story centers around a particularly cute computational problem. Given a list of (maybe negative) integers x1 through xN, find a and b so that the sum of xi from i = a to b is maximized. In other words, find the biggest-sum contiguous sublist of the original list of numbers.
Back in the 70s Ulf Grenander came up with the obvious O(n3) algorithm, noticed it was slow, and improved it to O(n2). He asked Shamos about it, who improved it to O(n lg n) by thinking about it overnight. Shamos told the story up to that point to Kadane, who in "a minute" improved it to O(n).
Exercise to the reader: what were the four algorithms?
I was very pleased that I was able to reconstruct them eventually, strangely repeating the fact that it took sleeping on it to think of the O(n ln n) (although in hindsight I really should have got that quicker) and then the O(n) solution seemed easy after that. It was strange how trying really hard last night to think of the O(n) algorithm directly failed, and really just served as a distracting force. Working in a more generous "budget" of n lg n made me stop worrying about being heroically clever and let me think about the problem more calmly.
