This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given an array `nums`

of integers, you can perform operations on the array.

In each operation, you pick any `nums[i]`

and delete it to earn `nums[i]`

points. After, you must delete **every** element equal to `nums[i] - 1`

or `nums[i] + 1`

.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

**Example 1:**

Input:nums = [3, 4, 2]Output:6Explanation:Delete 4 to earn 4 points, consequently 3 is also deleted. Then, delete 2 to earn 2 points. 6 total points are earned.

**Example 2:**

Input:nums = [2, 2, 3, 3, 3, 4]Output:9Explanation:Delete 3 to earn 3 points, deleting both 2's and the 4. Then, delete 3 again to earn 3 points, and 3 again to earn 3 points. 9 total points are earned.

**Note:**

`nums`

is at most `20000`

.`nums[i]`

is an integer in the range `[1, 10000]`

.b'

\n\n#### Approach #1: Dynamic Programming [Accepted]

\n

\n

'
**Intuition**

Because all numbers are positive, if we "take" a number (use it to score points), we might as well take all copies of it, since we\'ve already erased all its neighbors. We could keep a count of each number so we know how many points taking a number is worth total.

\nNow let\'s investigate what happens when we add a new number `X`

(plus copies) that is larger than all previous numbers. Naively, our answer would be the previous answer, plus the value of `X`

- which can be solved with dynamic programming. However, this fails if our previous answer had a number taken that was adjacent to `X`

.

Luckily, we can remedy this. Let\'s say we knew `using`

, the value of our previous answer, and `avoid`

, the value of our previous answer that doesn\'t use the previously largest value `prev`

. Then we could compute new values of `using`

and `avoid`

appropriately.

**Algorithm**

For each unique value `k`

of `nums`

in increasing order, let\'s maintain the correct values of `avoid`

and `using`

, which represent the answer if we don\'t take or take `k`

respectively.

If the new value `k`

is adjacent to the previously largest value `prev`

, then the answer if we must take `k`

is `(the point value of k) + avoid`

, while the answer if we must not take `k`

is `max(avoid, using)`

. Similarly, if `k`

is not adjacent to `prev`

, the answer if we must take `k`

is `(the point value of k) + max(avoid, using)`

, and the answer if we must not take `k`

is `max(avoid, using)`

.

At the end, the best answer may or may not use the largest value in `nums`

, so we return `max(avoid, using)`

.

Our demonstrated solutions showcase two different kinds of sorts: a library one, and a radix sort. For each language, the other kind of solution can be done without much difficulty, by using an array (Python) or HashMap (Java) respectively.

\n\n**Complexity Analysis**

- \n
- \n
Time Complexity (Python): , where is the length of

\n`nums`

. We make a single pass through the sorted keys of , and the complexity is dominated by the sorting step. \n - \n
Space Complexity (Python): , the size of our

\n`count`

. \n - \n
Time Complexity (Java): We performed a radix sort instead, so our complexity is where is the range of allowable values for

\n`nums[i]`

. \n - \n
Space Complexity (Java): , the size of our

\n`count`

. \n

\n

Analysis written by: @awice.

\n