Uma única operação com ações
A missão
Problema
Você recebe uma lista com os preços diários de uma ação, em que a posição i guarda o preço do dia i. Você pode comprar em um dia e vender em um dia estritamente posterior, no máximo uma vez. Retorne o maior lucro que essa única operação pode gerar. Se nenhum dia posterior pagar mais do que um anterior, retorne 0, porque a melhor jogada é não operar.
Exemplos
Input: prices = [8, 3, 6, 1, 9, 4]
Output: 8
Por quê: compre no dia 3 a 1, venda no dia 4 a 9
Input: prices = [7, 5, 4, 2]
Output: 0
Por quê: os preços só caem, então toda operação daria prejuízo
Input: prices = [5]
Output: 0
Por quê: edge case: um único dia não deixa nenhum dia posterior para vender
Dicas
0 / 3
Comparar cada dia de compra com cada dia de venda funciona, mas repete muito esforço. Pergunte-se o que uma única passada da esquerda para a direita poderia lembrar no lugar disso.
Conforme você avança no tempo, só dois fatos sobre o passado importam: o menor preço visto até agora e o melhor lucro encontrado até agora.
Percorra os dias uma vez. Em cada dia, primeiro calcule o lucro de vender hoje contra o menor preço anterior e guarde-o se ele bater o seu recorde; depois, reduza o menor preço corrente se o de hoje for mais barato que todos os anteriores.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Solução
Percorra os preços uma vez, carregando o menor preço visto até agora. Vender no dia atual vale o preço de hoje menos esse mínimo; comparar esse valor com o melhor lucro até agora mantém a resposta atualizada. Atualizar o mínimo depois de calcular a venda garante que o dia de compra seja sempre estritamente anterior ao dia de venda. O tempo é O(n), com uma única passada, e o espaço é O(1), já que só dois números são guardados.
def max_trade_profit(prices):
best = 0 # best profit found so far
cheapest = float("inf") # lowest price seen up to today
for p in prices:
# a sale today is only worth as much as the cheapest earlier buy
best = max(best, p - cheapest)
cheapest = min(cheapest, p)
return best
print(max_trade_profit([8, 3, 6, 1, 9, 4])) # -> 8
print(max_trade_profit([7, 5, 4, 2])) # -> 0
print(max_trade_profit([5])) # -> 0Travou na ideia, e não no código? Algoritmo de Kadane explica isso.