Ações da bolsa
Juninho é um menino muito visionário e inteligente, que quer ficar rico.
Aos 12 anos de idade, já está interessado em investimentos de ações na bolsa
de valores. Uma ação é como se fosse um pedaço de uma empresa que qualquer
pessoa pode comprar. E como cada empresa tem tamanhos e valores diferentes,
cada ação também tem diferentes valores, e esses valores mudam o tempo todo.
Suponha, por exemplo, que Juninho compre uma ação de uma empresa de petróleo,
que custe R$ 100. Suponha que no dia seguinte, essa empresa descubra um enorme
poço de petróleo, o que vai dar muitos lucros para ela no futuro. Essa empresa,
então, passa a ser mais valorizada, e conseqüentemente o preço das ações sobem. Suponha
que as ações subiram 20% nesse dia. Então Juninho, que tinha uma ação de R$ 100, hoje
tem a mesma ação, mas que vale R$ 120. Ou seja, se ele a vender hoje, vai ter
um lucro de R$ 20, só por ter comprado e vendido a ação.
Uma empresa de refrigerantes criou um novo tipo de investimento especial para iniciantes. Ela ocorre
da seguinte maneira:
- O investidor compra as ações da empresa na manhã do dia X;
- O dinheiro fica investido durante exatamente quatro dias seguidos;
- Ao final dos quatro dias, são aplicados juros simples ao
preço das ações; todas elas são vendidas e o dinheiro é dado de
volta ao investidor.
Por exemplo, suponha que as variações do preço das ações sejam:
- Dia 1: Aumento de 3%
- Dia 2: Aumento de 1%
- Dia 3: Queda de 2%
- Dia 4: Queda de 3%
- Dia 5: Aumento de 5%
- Dia 6: Queda de 5%
Se aplicarmos R$ 100 no dia 1, ao final do dia 4 vamos ter uma
variação de 3+1-2-3 = -1, ou seja, prejuízo de R$ 1. Mas se
começarmos aplicando no dia 2, ao final teremos uma variação de
1-2-3+5 = 1%, ou seja, lucro de R$ 1.
Juninho, que além de inteligente é também vidente (ou seja, consegue prever o
futuro), pediu a sua ajuda para descobrir qual é a maior quantidade de
dinheiro que ele pode lucrar investindo exatamente R$ 100,00 durante
quatro dias. Para isso, ele vai te dizer a variação das ações nos
próximos N dias seguidos, onde N ≥ 4.
Entrada
A entrada é composta por duas linhas. Na primeira, é dado um número
inteiro N,
indicando a quantidade de dias que Juninho já sabe qual será a
variação do valor da ação. Na segunda linha são dados N números inteiros Xi,
separados por espaços em branco, sendo
Xi a variação do preço das ações no dia i.
Saída
Seu programa deve imprimir na saída padrão uma única linha,
contendo um número inteiro indicando qual é o maior lucro que Juninho pode conseguir ao investir nos
dias que ele previu (o dinheiro não pode ficar investido em nenhum dia que ele não previu).
Note que o `lucro" pode na verdade ser prejuízo (lucro negativo), se as ações se
desvalorizarem.
Restrições
- 4 ≤ N ≤ 105
- -1000 ≤ Xi ≤ 1000
Informações sobre a pontuação
- Em um conjunto de casos de teste que totaliza 30 pontos, N ≤ 10 e $0 ≤ X_i ≤ 100.
- Em um conjunto de casos de teste que totaliza 55 pontos, N ≤ 100 e -100 ≤ X_i ≤ 100.
Exemplos
Entrada
5
3 1 -2 -3 5
|
Saída
1
|
Entrada
6
-2 1 -2 1 0 -3
|
Saída
0
|
Entrada
8
-1 -2 -3 -4 -5 -6 -7 -8
|
Saída
-10
|
