March
18th,
2013

blog comments powered by Disqus
Another week, another interesting puzzle. This puzzle is taken from a programming exercise posed by *Martin Rem* in 1988

A Surpassing Problem

By definition, a surpasser of an element of an array is a greater element to the right, so x[j] is a surpasser of x[i] if i < j and x[i] < x[j]. The surpasser count of an element is the number of surpassers. For example, the surpasser count of the string GENERATING are given by

`G E N E R A T I N G`

`5 6 2 5 1 4 0 I 0 0`

The maximum surpasser count is 6. The first occurrence of the letter E has six surpassers, namely N, R, T, I, N, and G. Remâ€™s problem is to compute the maximum surpasser count of an array of length n > 1 and to do so with an O(n log n) algorithm.