Pular para o conteúdo

Colheita sem vizinhos

Fácil#bottom-up-dp#rolling-variables~20 min

A missão

Problema

Um robô de colheita percorre uma única fileira de lotes, e cada lote tem uma produção conhecida. O braço dele precisa descansar depois de cada colheita, então ele nunca pode colher dois lotes que ficam lado a lado. Retorne a maior produção total que o robô consegue juntar em uma única passada. As produções são números inteiros a partir de 0, e a fileira pode estar vazia.

Exemplos

Input:  yields = [2, 7, 9, 3, 1]
Output: 12
Por quê: colha os lotes 0, 2 e 4 para obter 2 + 9 + 1
Input:  yields = [5, 1, 1, 5]
Output: 10
Por quê: os dois lotes das pontas não são vizinhos, então os dois podem ser colhidos
Input:  yields = []
Output: 0
Por quê: edge case: uma fileira vazia não produz nada

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(1)

Restrições

  • yields are integers ≥ 0
  • the row may be empty

Travou na ideia, e não no código? House Robber explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado