You are given an integer array nums. In one operation you pick a value, earn that many points, and then must delete every element equal to value - 1 and value + 1.
Return the maximum number of points you can earn.
We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
You are given an integer array nums. In one operation you pick a value, earn that many points, and then must delete every element equal to value - 1 and value + 1.
Return the maximum number of points you can earn.
A medium dynamic programming problem, graded against 7 test cases (5 of them hidden).
Overlapping subproblems solved once and reused - the pattern candidates fear most.
Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.
More Dynamic Programming problems →House Robber on value buckets. Sum points for each value into `points[v]`. Taking `v` forbids `v-1` and `v+1`, so this is the House Robber recurrence over the value axis: `cur = max(cur, prev + points[v])`.
Time: O(n + maxVal). Space: O(maxVal).
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.