Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2463
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2463
Corredor
Por OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
Bruninho está programando um personagem virtual para o próximo desafio de um jogo de aventura em que, numa das fases, o personagem tem que entrar em um corredor, percorrer algumas salas e depois sair do corredor. Ele pode entrar apenas uma vez, e passar por cada sala apenas uma vez. Todas as salas possuem uma porta de entrada e uma de saída, como ilustra a parte (a) da figura abaixo. Ao passar por uma sala o jogador ganha um certo número de vidas (que pode ser negativo!). O objetivo é passar pelo corredor coletando a maior quantidade possível de vidas! Por sorte, sempre existe ao menos uma sala onde se ganha um número positivo de vidas.
No exemplo acima, o personagem de Bruninho pode ganhar, no máximo, 12 vidas, por exemplo, entrando pela sala 2 e saindo pela sala 4, como mostrado na parte (b) da figura. Nesta tarefa, você deve escrever um programa que, dados os números de vidas correspondentes a cada sala do corredor, calcule a quantidade máxima de vidas que será possível ganhar.
Entrada
A entrada é composta por duas linhas. A primeira linha contém um inteiro N (1 ≤ N ≤ 50000), o número de salas no corredor. A segunda linha contém N números inteiros (entre −100 e 100), positivos ou negativos, indicando a quantidade de vidas que se ganha em cada sala.
Saída
Seu programa deve imprimir uma linha, com o número máximo de vidas que é possível ganhar.
| Exemplos de Entrada | Exemplos de Saída |
|
7 |
12 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
using namespace std;
int main() {
int n, m1 = 0, m2 = 0, d;
scanf("%d", &n);
while (n--) {
scanf("%d", &d);
m1 = max(0, m1 + d);
m2 = max(m1, m2);
}
printf("%d\n", m2);
return 0;
}
Input
-2 5 -1 8 -11 7 3
Output
#2 Code Example with Python Programming
Code -
Python Programming
n=int(input())
a=list(map(int,input().split()))
soma=aux=0
for i in a:
soma+=i
aux=max(aux,soma)
if soma<0:soma=0
print(aux)
Input
-2 5 -1 8 -11 7 3
Output