Sunny Orchard Row
A community garden has one long row of plots for fruit trees. From soil tests and sunlight, the gardeners know how many kilograms of fruit a tree would give in each plot. The catch: a tree crowds the roots of its neighbours, so two trees in plots right next to each other both do badly. So the gardeners never plant in two neighbouring plots.
If they choose the plots well, how much fruit can the row give?
Your task
Write maxHarvest(yields). yields[i] is the harvest in kilograms if plot i gets a tree. Choose any set of plots with no two neighbours (plots i and i + 1) both chosen, and return the largest possible total harvest.
You may leave plots empty. An empty row gives 0.
maxHarvest(yields: int[]) → int
Examples
yields = [6, 2, 3, 9, 1]
15
Plant in plots 0 and 3: 6 + 9 = 15. Planting every other plot gives 6 + 3 + 1 = 10 or 2 + 9 = 11. The best choice leaves two plots in a row empty (plots 1 and 2), which the every-other pattern never does.
yields = [4, 7, 4]
8
The best single plot is 7, but taking it blocks both neighbours. Taking the two 4s gives 8, which is more.
Constraints
- 0 ≤ yields.length ≤ 1,000
- 0 ≤ yields[i] ≤ 10,000
Start with brute force
Try every subset of plots, skip the ones with two neighbours, and keep the best total. With 1,000 plots there are 2¹⁰⁰⁰ subsets, far too many. Even the valid ones grow exponentially.
Two shortcuts look tempting and are wrong. Taking every other plot fails on [6, 2, 3, 9, 1]. Grabbing the biggest yield first fails on [4, 7, 4].
Hints
0 of 4 shown- Hint 1
Look at the last plot in
[6, 2, 3, 9, 1]. In the best plan, either it has a tree or it does not. What does each case tell you about the rest of the row? - Hint 2
If the last plot is empty, the answer is the best plan for the row without it. If it has a tree, its neighbour must be empty, so the answer is its yield plus the best plan for the row without the last two plots.
- Hint 3
Let
best(i)be the most fruit from plots 0 toi. Thenbest(i) = max(best(i - 1), best(i - 2) + yields[i]). What arebestfor an empty row and for one plot? - Hint 4
Walk left to right keeping only two numbers: the best for the row up to the previous plot, and up to the plot before that. At each plot, compute the new best from those two and shift them along.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Make one decision per plot, from left to right: plant or skip. If you skip plot i, you keep the best from plots before it. If you plant, plot i - 1 must be empty, so you add yields[i] to the best from two plots back. Take the larger.
Trace [6, 2, 3, 9, 1], writing best after each plot:
- Plot 0 (6): max(0, 0 + 6) = 6.
- Plot 1 (2): max(6, 0 + 2) = 6. Skipping is better.
- Plot 2 (3): max(6, 6 + 3) = 9.
- Plot 3 (9): max(9, 6 + 9) = 15. Planting here builds on the best up to plot 1, which was just plot 0.
- Plot 4 (1): max(15, 9 + 1) = 15. Answer 15.
Notice step 4: the plan it builds on skips both plot 1 and plot 2. The recurrence finds that on its own, because best already carries the right choice for every shorter row.
function maxHarvest(yields) {
let prev2 = 0; // best for the row up to two plots back
let prev1 = 0; // best for the row up to the previous plot
for (const y of yields) {
// skip this plot, or plant here and skip the neighbour
const best = Math.max(prev1, prev2 + y);
prev2 = prev1;
prev1 = best;
}
return prev1;
}def max_harvest(yields):
prev2 = 0 # best for the row up to two plots back
prev1 = 0 # best for the row up to the previous plot
for y in yields:
# skip this plot, or plant here and skip the neighbour
best = max(prev1, prev2 + y)
prev2, prev1 = prev1, best
return prev1Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.