Soma máxima em um intervalo Adaptado por Aléssio Jr

Dada uma sequência qualquer \(S=(s_1,s_2,s_3,...,s_n)\) qual a maior soma que podemos obter escolhendo um subconjunto de termos adjacentes de \(S\)? Se a sequência for, por exemplo, \((1,-3,5,-2,1,-1)\), a soma máxima é \(4\), com os termos \((5,-2,1)\).

Este é um dos problemas gulosos mais clássicos da programação, entretanto, esconde uma ideia de programação dinâmica por trás. Se \(v_i\) é a maior soma possível para um subconjunto de termos adjacentes que termina em \(i\), então temos apenas duas opções para \(v_{i+1}\): ou zero (não usar o elemento \(i\) ou o usamos, adicionando a maior soma possível que antes dele, em \(i\), ou seja, \(v_i+s_{i+1}\). Desse modo, \(v_{i+1}=max(0,s_{i+1}+v_i)\)

Assim, o algoritmo fica extremamente simples: vou guardar uma variável maior que guardará a melhor soma de elementos adjacentes que termina exatamente no elemento em que estamos. Depois, vou percorrer o a sequência. Assim que chego no elemento \(i\), maior guarda o melhor resultado para a casa anterior, logo, posso usá-lo para calcular a maior soma que termina no elemento em que estamos, que é \((max(0,s_i+ant)\), sendo este, portanto, o novo valor de maior. Se isso superar o maior valor dentre todos os que já tivemos, ele será a nova resposta.

Note também, que, no começo, maior é zero, pois a maior soma que conseguimos obter com elementos anteriores ao primeiro é zero, pois não há escolha.

Segue, para melhor entendimento, o código de uma função que recebe o endereço de um vetor de inteiros como parâmetro, e retorna a maior soma possível de elementos adjacentes dele:

            #include <algorithm>
            int max_sum(vector<int> s){

                int resp=0, maior=0;

                for(int i=0;i<s.size();i++){

                    maior=max(0,maior+s[i]);

                    resp=max(resp,maior);
                }

                return resp;
            }