Saltar al contenido

Cosecha sin parcelas vecinas

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

La misión

Problema

Un robot cosechador recorre una sola fila de parcelas, y cada parcela tiene un rendimiento conocido. Su brazo necesita descansar después de cada recolección, así que nunca puede cosechar dos parcelas que estén una al lado de la otra. Devuelve el mayor rendimiento total que el robot puede recoger en una pasada. Los rendimientos son números enteros desde 0 en adelante, y la fila puede estar vacía.

Ejemplos

Input:  yields = [2, 7, 9, 3, 1]
Output: 12
Por qué: cosechas las parcelas 0, 2 y 4 para obtener 2 + 9 + 1
Input:  yields = [5, 1, 1, 5]
Output: 10
Por qué: las dos parcelas de los extremos no son vecinas, así que se pueden tomar ambas
Input:  yields = []
Output: 0
Por qué: caso límite: una fila vacía no rinde nada

Pistas

0 / 3

Tiempo objetivo
O(n)
Espacio objetivo
O(1)

Restricciones

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

¿Lo que te frena es la idea y no el código? House Robber lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio