FAST ALGORITHMS FOR THE MAXIMUM CONVOLUTION PROBLEM

We describe two algorithms for solving the maximum convolution problem, i.e. the calculation of c(k): = max {a(k-i) + b(i)\0 less-than-or-equal-to i less-than-or-equal-to n-1} for all k with respect to given sequences (a0, ..., a(n-1)), (b0, ..., b(n-1), of real numbers. Our first algorithm with expected running time 0(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.