c_k := max { a_{k-i} + b_i | 0 =< i <= n-1 } for all k
with respect to given sequences (a_0,...,a_{n-1}),
(b_0,...,b_{n-1}) of real numbers. Our first algorithm with
expected running time O(n log n) is mainly of theoretical interest
while our second algorithm allows a simpler, more practicable
implementation and showed quite fast performance in numerical
experiments.
Keywords: maximum convolution; probabilistic analysis