id: 04145299
dt: j
an: 04145299
au: Rem, M.
ti: Small programming exercises 24.
so: Sci. Comput. Program. 14, No.1, 97-101 (1990).
py: 1990
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: 
ut: convex neighbour equality; lexicographically greatest subsequence
ci: 
li: doi:10.1016/0167-6423(90)90060-Q
ab: Summary: A function f is called convex if f(i) does not exceed the average
    of f(i- 1) and $f(i+1)$. Examples of convex functions are $f(x)=0$ and
    $f(x)=x\sp 2$. Exercise 55 deals with an array that represents a convex
    function. We have to check whether the array contains equal consecutive
    elements. This problem may be solved in O(log N) time for an array of
    size N. I owe this problem to Jan L. A. van de Snepscheut. A
    subsequence of a sequence is one that can be obtained by deleting zero
    or more elements from the original sequence. Exercise 56 asks to write
    a program that determines the lexicographically greatest subsequence of
    a given sequence. It allows a solution with an execution time that is
    linear in the length of the given sequence. This problem is due to Anne
    Kaldewaij.
rv: