FunctionRacerProblemsRace

Gems That Clash

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems