> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/740-deleteand-earn.md).

# 740     Delete and Earn

## 740. [Delete and Earn](https://leetcode.com/problems/delete-and-earn/description/)

## 1. Question

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: 6

Explanation:

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: 9

Explanation:

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:**

The length of`nums`is at most`20000`.

Each element`nums[i]`is an integer in the range`[1, 10000]`.

## 2. Implementation

**(1) DP**

思路:

(1) 这题由于选择了一个数后，就必须把比这个数小1或比这个数大于1的数给删除，所以我们需要用一个方法可以**表示所有连续数字**，由于数字的范围在1 - 10000,所以直接建立一个size为10000的数组dp

(2) 对于每个数，我们只有两种操作, earn it or skip it, 如果我们要earn的话，就要跳过比当前数少1的数，如果skip当前的数，则取之前的数，所以可以得到状态转移方程:

dp\[i] = Math.max(dp\[i - 1], dp\[i - 2] + dp\[i]);

(3) 上面的dp有两层含义，在第一步初始化dp数组时，dp\[i]表示数字i的值总和 比如数组\[3, 3, 3]，dp\[3] = 9。在第二步中我们要找到最大可以earn的值的时候，dp\[i]此时的含义是在前\[1-i]中，我们通过earn和delete的操作，可以得到的最大的值

```java
class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = 10001;
        int[] dp = new int[n];

        for (int num : nums) {
            dp[num] += num;
        }

        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + dp[i]);
        }
        return dp[n - 1];
    }
}
```

**(2) 空间优化**

```java
class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = 10001;
        int[] dp = new int[n];

        for (int num : nums) {
            dp[num] += num;
        }

        int skip = 0, take = 0;
        for (int i = 0; i < n; i++) {
            int takei = skip + dp[i];
            int skipi = Math.max(skip, take);
            take = takei;
            skip = skipi;
        }
        return Math.max(skip, take);
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(n), 空间复杂度O(1), 空间虽然是O(1)，但实际上size是10001，涵盖数的所有范围

**空间优化:** 时间复杂度O(n), 空间复杂度O(1)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/740-deleteand-earn.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.