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.
Read full article from Puzzle - A surpassing problem
No comments:
Post a Comment