Non-Adjacent Harvest
Problem
A harvesting robot drives along a single row of plots, and each plot holds a known yield. Its arm needs a rest after every pick, so it can never harvest two plots that sit next to each other. Return the largest total yield the robot can collect in one pass. Yields are whole numbers from 0 upward, and the row may be empty.
Examples
Input: yields = [2, 7, 9, 3, 1]
Output: 12
Why: harvest plots 0, 2 and 4 for 2 + 9 + 1Input: yields = [5, 1, 1, 5]
Output: 10
Why: the two end plots are not neighbours, so both can be takenInput: yields = []
Output: 0
Why: edge case, an empty row yields nothingHints
0 / 3
Picking the biggest plot first can block two good neighbours. Think about the row one plot at a time instead of all at once.
When you reach a plot you face exactly one decision: harvest it or skip it. Each choice only depends on what happened at the plot just before.
Carry two running totals: the best result if the previous plot was harvested, and the best if it was skipped. Harvesting the current plot extends the skipped total; skipping it keeps the better of the two.
Solution
At every plot the best total so far comes from one of two states: the previous plot was harvested, or it was not. Harvesting the current plot is only allowed from the skipped state, and skipping it keeps whichever state was better, so two variables replace a whole table. The answer is the better state after the last plot. Time is O(n) with one pass, and space is O(1).
def best_harvest(yields):
took, skipped = 0, 0 # best total if the last plot was harvested / left alone
for y in yields:
# harvesting now needs the previous plot skipped; skipping keeps the better state
took, skipped = skipped + y, max(took, skipped)
return max(took, skipped)
print(best_harvest([2, 7, 9, 3, 1])) # -> 12
print(best_harvest([5, 1, 1, 5])) # -> 10
print(best_harvest([])) # -> 0Stuck on the idea rather than the code? House Robber covers it.