[en] ON THE LOWER BOUND FOR THE MAXIMUM CONSECUTIVE SUB-SUMS PROBLEM - WILFREDO BARDALES RONCALLA (2014)
[pt] O Problema das Sub-somas Consecutivas Máximas (MCSP) surge em cenários de interesse teórico e prático, por exemplo, no casamento aproximado de padrões, identificação de proteínas e análise de dados estatísticos apenas para nomear alguns. Dada uma sequência de n números reais não negativos, O MCSP consiste em calcular as somas consecutivas máximas de tamanho 1 até n. Como existem implementações triviais que permitem encontrar o máximo para um comprimento fixo, existe um procedimento quadrático simples que permite resolver o MCSP. Apesar dos esforços dedicados ao problema, não é conhecido nenhum algoritmo significativamente melhor que a solução simples. Portanto, uma pergunta natural é se existe um limite inferior superlinear para o MCSP. Neste trabalho reportamos nossas pesquisas no sentido de provar tal limite.