Gems That Clash
Each number in gems is the value of one gem. Choose any of the gems to keep, with one rule: if you keep a gem of value v, you may not keep any gem of value v - 1 or v + 1. Gems of equal value never clash with each other.
Return the largest total value of the gems you keep. Keeping nothing is allowed and gives 0.
Example 1
gems [2,2,3,3,3,4]
returns 9
Keep the three 3s for 9. Keeping both 2s and the 4 instead gives only 8.
Example 2
gems [5,1,6,2,7]
returns 14
Keep 2, 5 and 7: no two of them differ by exactly 1.
Constraints
0 <= len(gems) <= 1001 <= gems[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Hands That Hit the TargetMedium
- Keystrokes to TransformMedium
- Knight on the KeypadMedium
- Letter DecodingsMedium
- Lightest Deletions to MatchMedium
- Longest Climbing ChainMedium
- Longest Insertion LadderMedium
- Longest Mirror SubsequenceMedium