Best Time to Buy and Sell Stock

Você recebe o preço de uma ação ao longo de vários dias, um preço por dia. Você pode comprar uma ação em algum dia e vendê-la em um dia posterior. O lucro é o preço de venda menos o preço de compra, e você quer obter o maior lucro possível. Se todas as negociações resultarem em prejuízo, basta não negociar e ganhar 0.

Considere os preços [7, 2, 5, 9, 1, 4]. Comprar por 2 no dia 1 e vender por 9 no dia 3 gera 7, e nenhum outro par de dias dá um resultado melhor. Comprar por 1 no dia 4 parece tentador porque é o dia mais barato, mas o único dia posterior tem preço de venda 4, então essa negociação gera apenas 3.

Tentar todos os pares de dias funciona, mas é lento demais para listas de preços longas. Em vez disso, você pode fazer uma única passagem pelos dias. Se você vender hoje, o melhor dia para ter comprado é o dia mais barato até agora; então, mantenha esse menor preço à medida que avança. O melhor lucro de hoje é o preço de hoje menos o menor preço, e a resposta é o maior desses valores.

Escreva uma função chamada maxProfit que recebe uma lista de inteiros prices, em que prices[i] é o preço da ação no dia i, e retorna o maior lucro que você pode obter comprando em um dia e vendendo em um dia posterior. Se nenhuma negociação gerar lucro, retorne 0.

Restrições: 1 ≤ prices.length ≤ 10^5, 0 ≤ prices[i] ≤ 10^4.