Harvest Without Neighbours
Medium1-D Dynamic Programming
Problem
A warehouse holds crates, each labelled with a positive integer; labels lists them (labels may repeat). You collect crates and score the sum of their labels.
There is one rule: if you collect any crate labelled v, you may not collect any crate labelled v - 1 or v + 1. Return the highest score you can reach.
Example 1
- Input:
- labels = [3, 4, 2]
- Output:
- 6
Collect 4 and 2 (3 is then forbidden): 6. Collecting 3 alone gives only 3.
Example 2
- Input:
- labels = [2, 2, 3, 3, 3, 4]
- Output:
- 9
Collect the three 3s: 9.
Constraints
- 1 ≤ labels.length ≤ 2·10^4
- 1 ≤ labels[i] ≤ 10^4
Hint
Show the first hint
If you collect one crate labelled v, is there any reason not to collect every crate labelled v?
Walkthrough
How to approach it
01Clarify before coding
- Are labels positive? Yes, so collecting more crates of an allowed label never hurts.
- Does the rule apply to equal labels? No, only to labels exactly one apart.
- How large can labels be? Up to 10^4, small enough to index an array by label.
02Brute force
Try every subset of distinct labels with no two consecutive, scoring v × count(v) for each chosen label.
Cost: O(2^d · d) for d distinct labels: impossible with thousands of labels.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.