Comprar e vender ações
Dado
n inteiros que representam os preços da ação da sua empresa favorita, pretende decidir qual seria a melhor altura para comprar e vender a ação. Só quer comprar a ação uma vez e vendê-la apenas uma vez. Portanto, o seu objetivo é maximizar o lucro (comprar barato e vender caro).Determine qual o lucro máximo que pode obter com esta ação, e se não existir nenhuma forma de obter lucro, deve imprimir 0 (significando que não irá comprar ou vender a ação).
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).A linha seguinte contém
n inteiros separados por espaços , que representam os preços da ação (0 ≤ ≤ 1000).Saída
O programa deve imprimir o lucro máximo que pode obter ao comprar e vender a sua ação favorita.
Exemplos
Input | Output |
5
4 2 6 8 1 | 6 |
4
8 6 4 3 | 0 |
Explicação
- Compramos quando o valor da ação está a 2 e vendemos quando está a 8
- Não é possível obter lucro pois o valor da ação está sempre a descer
Sugestão
Em cada momento, pode manter um estado do “melhor” resultado possível até ao momento e outro valor para o preço mais baixo que já foi registado.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB