Solução de Frederico Bulhões
Para resolver esse problema podemos usar um algoritmo conheciodo como algoritmo de Sublista Contígua de Soma Máxima, usando o algoritmo de Kadane.
Em resumo o algoritmo de Kadane calcula a maior soma terminando em cada posição do vetor, usando programação dinâmica, e por fim calcula o máximo desses máximos.
Código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // codigo de Larissa Mesquita | |
| #include <iostream> | |
| using namespace std; | |
| #define MAX 50010 | |
| int v[MAX], n; | |
| int f(){ | |
| int atual=0, maior=0; | |
| for(int i=0;i<n;i++){ | |
| atual=max(0, atual+v[i]); | |
| maior=max(maior, atual); | |
| } | |
| return maior; | |
| } | |
| int main(){ | |
| cin>>n; | |
| for(int i=0;i<n;i++) | |
| cin>>v[i]; | |
| cout<<f()<<endl; | |
| } |