delete-and-earn

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code>. You want to maximize the number of points you get by performing the following operation any number of times:

<ul>
	<li>Pick any <code>nums[i]</code> and delete it to earn <code>nums[i]</code> points. Afterwards, you must delete every element equal to <code>nums[i] - 1</code> and every element equal to <code>nums[i] + 1</code>.</li>
</ul>

Return the maximum number of points you can earn by applying the above operation some number of times.

&nbsp;
Example 1:

<pre>
Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.
</pre>

Example 2:

<pre>
Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2&#39;s and 4&#39;s are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 104</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 104</code></li>
</ul>

deleteAndEarn

Delete and Earn

House Robber

house-robber

打家劫舍

Array

Hash Table

Dynamic Programming

给你一个整数数组 <code>nums</code> ，你可以对它进行一些操作。

每次操作中，选择任意一个 <code>nums[i]</code> ，删除它并获得 <code>nums[i]</code> 的点数。之后，你必须删除 所有 等于 <code>nums[i] - 1</code> 和 <code>nums[i] + 1</code> 的元素。

开始你拥有 <code>0</code> 个点数。返回你能通过这些操作获得的最大点数。

 

示例 1：

<pre>
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
</pre>

示例 2：

<pre>
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
</pre>

 

提示：

<ul>
	<li><code>1 <= nums.length <= 2 * 104</code></li>
	<li><code>1 <= nums[i] <= 104</code></li>
</ul>