Searching for a superlinear lower bounds for the Maximum Consecutive Subsums Problem and the (min,+)-convolution

Wilfredo Bardales Roncalla, Eduardo Laber, Ferdinando Cicalese

Given a sequence of n numbers, the Maximum Consecutive Subsums Problem (MCSP) asks for the maximum consecutive sum of lengths l for each l = 1,...,n. No algorithm is known for this…