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-eq ual-to i less-than-or-equal-to n-1} for all k with respect to given se quences (a0, ..., a(n-1)), (b0, ..., b(n-1), of real numbers. Our firs t algorithm with expected running time 0(n log n) is mainly of theoret ical interest while our second algorithm allows a simpler, more practi cable implementation and showed quite fast performance in numerical ex periments.