Você recebe um array prices, onde prices[i] é o preço de uma ação no dia i.
Encontre o lucro máximo. Você pode fazer quantas transações quiser (comprar e depois vender), com duas regras:
· Você só pode ter uma ação por vez: precisa vender antes de comprar de novo.
· Depois de vender, vem um dia de cooldown: no dia seguinte à venda você não pode comprar.
Exemplo 1 · prices = [1, 2, 3, 0, 2] → 3
Comprar (1), vender (2), cooldown, comprar (0), vender (2). Lucro (2−1) + (2−0) = 3. Vender no 3 daria 2,
mas o cooldown impediria comprar no 0.
Tabulation com uma máquina de estados: em cada dia você está em
um de 3 estados, e dp[i][estado] guarda o maior lucro possível terminando o dia i naquele estado.
Cada linha depende só da linha anterior.
comprar (−preço)
┌──────┐ ────────────────▶ ┌──────┐
│ REST │ │ HOLD │
└──────┘ └──────┘
▲ │
│ fim do cooldown │ vender (+preço)
│ ┌──────┐ │
└───────── │ SOLD │ ◀───────┘
└──────┘
HOLD e REST também podem se manter de um dia para o outro (segurar / descansar). SOLD não: dura só o dia da venda.
tempo O(n)espaço O(n)
Um dia por vez, 3 estados por dia.
prices
dia atual
registradores
tabela dp[i] = [hold, sold, rest]
leitura 1leitura 2escrita░░ não inicializado
código
memória · bloco contíguo row-major
n linhas × 3 estados: O(n) de espaço, 12 B por dia. Borda rosa = início de cada dia.
Na versão com matriz cada dia só lê o dia anterior,
então bastam 3 variáveis. Só que a sobrescrita tem um problema: as dependências formam um
ciclo. sold precisa do hold antigo, hold precisa do
rest antigo e rest precisa do sold antigo. Qualquer ordem de atualização
destrói um valor que ainda vai ser lido, e por isso salvamos o sold antigo numa 4ª célula,
tmp. Compare com o knapsack (loop reverso) e o Predict the Winner (loop para frente): aqui nenhuma
ordem resolve sozinha.
comprar (−preço)
┌──────┐ ────────────────▶ ┌──────┐
│ REST │ │ HOLD │
└──────┘ └──────┘
▲ │
│ fim do cooldown │ vender (+preço)
│ ┌──────┐ │
└───────── │ SOLD │ ◀───────┘
└──────┘
HOLD e REST também podem se manter de um dia para o outro (segurar / descansar). SOLD não: dura só o dia da venda.
tempo O(n)espaço O(1)
Só os 3 estados do dia anterior mais um temporário.
prices
dia atual
registradores
variáveis
leitura 1leitura 2escritadia k dia a que o valor pertence
código
memória · O(1)
Sempre 4 células (16 B), seja com 5 ou com 5000 dias. A matriz usaria n·3·4 B.
Memoization (top-down): f(i, h) = maior lucro do dia i em
diante, estando h = 0 (livre) ou h = 1 (segurando a ação). Em cada dia há duas opções:
esperar (f(i+1, h)) ou agir. Livre, agir é comprar:
f(i+1, 1) − preço. Segurando, agir é vender, e o cooldown pula um dia: preço + f(i+2, 0).
Caminhos diferentes chegam ao mesmo (dia, estado), e o memo evita recalcular. São só 2·n estados.
tempo O(n)espaço O(n)
2n estados f(i, h), cada um em O(1). Memo n×2 e call stack de até n frames.
prices
dia atual
registradores
memo[i] = [livre, segurando]
leitura · cache hitescrita░░ ainda não calculado
código
call stack
memória · heap (memo)
memo O(n) no heap e call stack de até ~n frames. Com prices.length = 5000, essa profundidade
chega perto do limite da stack em várias linguagens. Aí a tabulação é a escolha segura.