Best Time to Buy and Sell Stock

+10

Você recebe uma lista prices, em que prices[i] é o preço de uma ação no dia i. Você pode comprar uma ação em um dia e vendê-la em um dia posterior. Retorne o maior lucro que você pode obter ou 0 quando todas as negociações possíveis resultarem em prejuízo.

Função

maxProfit(prices: integer-array) → integer

pricesinteger-array: o preço da ação em cada dia, em ordem
Retornainteger: o maior lucro obtido com uma compra e uma venda posterior, ou 0

Restrições

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴
Você faz no máximo uma operação e vende em um dia posterior ao dia em que compra.

Exemplos

Entrada: prices = [7, 2, 5, 9, 1, 4]
Saída: 7
Explicação: Compre no dia 1 por 2 e venda no dia 3 por 9, obtendo um lucro de 7. O preço mais baixo, 1 no dia 4, ocorre depois do 9, então a melhor venda depois dele rende apenas 3.

Para ir além

E se você pudesse fazer quantas negociações quisesse, mantendo no máximo uma ação por vez?

Solução

Você precisa comprar antes de vender, então a resposta não é o preço mais alto menos o mais baixo. Para cada dia em que você poderia vender, a melhor compra é no dia mais barato anterior a ele. Manter esse menor preço enquanto avança transforma o problema em uma única passagem.

Tente cada par de compra e venda

Correta, mas não termina nos maiores testes

Intuição

Cada negociação tem um dia de compra e um dia posterior de venda, então teste todos os pares e guarde a maior diferença. Começar o melhor lucro em 0 contempla a opção de não negociar. Todas as negociações permitidas são verificadas, então a resposta está correta.

Uma lista de n preços tem cerca de n²/2 pares: 100.000 dias significam cerca de 5 bilhões de subtrações.

Algoritmo

Defina best como 0.
Percorra todos os dias de compra buy.
Para cada um, percorra todos os dias de venda sell posteriores a ele.
Calcule prices[sell] menos prices[buy] e armazene o resultado em best se for maior.
Retorne best.

def maxProfit(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

Uma passagem com o menor preço até agora

Intuição

Fixe o dia de venda i. O melhor dia para ter comprado é o dia mais barato até i, então a melhor negociação que termina no dia i rende prices[i] menos o menor preço até então. Cada dia de venda é pareado com seu melhor dia de compra, então o maior desses lucros é a resposta. Em um dia que estabelece um novo mínimo, o lucro é 0, o mesmo que não negociar.

A iteração lê cada preço uma vez e mantém dois números, lowest e best: tempo O(n) e espaço O(1).

Algoritmo

Defina lowest como o primeiro preço e best como 0.
Percorra os preços em ordem.
Se o preço atual for menor que lowest, defina-o como o novo lowest.
Calcule o preço atual menos lowest e armazene o resultado em best se ele for maior.
Retorne best.

def maxProfit(prices):
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        elif price - lowest > best:
            best = price - lowest
    return best

Armadilhas e casos extremos

Retornar o maior preço menos o menor preço. Em [7, 2, 5, 9, 1, 4], isso resulta em 8, mas o 1 vem depois do 9. A resposta é 7.
Deixar a resposta ficar negativa. Em [9, 7, 4, 3, 1], a melhor diferença é -1; comece best em 0, não na primeira diferença.
Começar lowest em 0. Todo lucro será então igual ao próprio preço, então [9, 7, 4, 3, 1] retorna 9. Comece pelo primeiro preço.

Perguntas frequentes3

Qual é a complexidade de tempo de Melhor Momento para Comprar e Vender Ações?

A solução de uma única passagem leva O(n) de tempo para n dias, pois lê cada preço uma vez, e usa O(1) de espaço extra: o menor preço até então e o melhor lucro. Testar cada par de dias leva O(n²) de tempo.

Por que não subtrair o preço mais baixo do preço mais alto?

O menor preço pode vir depois do maior, e você precisa comprar antes de vender. Em [7, 2, 5, 9, 1, 4], o 1 vem depois do 9, então a melhor operação permitida compra por 2 e vende por 9, com lucro de 7.

Is Best Time to Buy and Sell Stock um problema de programação dinâmica?

Você pode interpretá-lo de qualquer uma das formas. O menor preço até agora é um pequeno estado que você atualiza a cada dia, que é a perspectiva da programação dinâmica. Associar cada venda ao dia anterior mais barato é a perspectiva gulosa. Ambas levam ao mesmo código de uma única passagem.

def maxProfit(prices):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

prices = [7, 2, 5, 9, 1, 4]

Saída Esperada