Maximum subarray problem

rdf:langString Sublista contígua de soma máxima

rdf:langString Em Ciência da Computação, encontrar a sublista contígua de maior soma a partir de uma lista de números é um problema bastante conhecido. Na seqüência acima, a sublista contígua de maior soma é [20, 50, -1, 3] e a soma total desse trecho é 72. Tipicamente, a lista de números a ser computada como entrada deve ter números positivos e negativos. Dessa forma, ao encontrar um número negativo vizinho a uma sublista de maior soma computada até então, uma das dificuldades do problema no decorrer da sua resolução é avaliar se esse número negativo deve ser acrescido à sublista ou não. Essa avaliação é necessária porque depois de um número negativo poderão vir na seqüência um ou mais números positivos que compensem o decréscimo resultante da inclusão daquele número negativo. Por outro lado, esse mesmo número negativo vizinho poderá não ser incorporado à sublista de maior soma, pois o resultado final seria uma soma menor do que a obtida até então. Para uma lista que contenha apenas números positivos, o resultado de maior soma será simplesmente a lista inteira dada como entrada. Nos algoritmos que serão apresentados a seguir, quando uma lista de números negativos é dada como entrada ou ainda se uma sublista parcial computada ao longo da resolução do problema resultar numa soma negativa, o resultado deverá ser zero, ou seja, o equivalente a obter como resposta uma lista vazia.