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 | 6 |
4 | 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