0740 补充英文解和Solution.java

gengyuanzhe · gengyuanzhe · commit 635dcfd42de7 · 2020-08-21T21:32:23.000+08:00
diff --git a/solution/0700-0799/0740.Delete and Earn/README.md b/solution/0700-0799/0740.Delete and Earn/README.md
@@ -46,16 +46,16 @@
 <!-- tabs:start -->
 核心思路: **一个数字要么不选，要么全选**
 
-首先计算出每个数字的总和sums，并维护两个dp数组：select和nonSelect
+首先计算出每个数字的总和 sums，并维护两个 dp 数组：select 和 nonSelect
 
-- sums[i]代表值为i的元素总和
-- select[i]代表如果选数字i，从0处理到i的最大和
-- nonSelect[i]代表如果不选数字i，从0处理到i的最大和
+- sums[i] 代表值为 i 的元素总和
+- select[i] 代表如果选数字 i，从 0 处理到 i 的最大和
+- nonSelect[i] 代表如果不选数字 i，从 0 处理到 i 的最大和
 
 那么我们有以下逻辑：
 
-- 如果选i，那么i-1肯定不能选；
-- 如果不选i，那么i-1选不选都可以，因此我们选择其中较大的选法
+- 如果选 i，那么 i-1 肯定不能选；
+- 如果不选 i，那么 i-1 选不选都可以，因此我们选择其中较大的选法
 
 ``` java
 select[i] = nonSelect[i-1] + sums[i];
@@ -78,24 +78,27 @@ class Solution {
         if (nums.length == 0) {
             return 0;
         }
+
         int[] sums = new int[10010];
+        int[] select = new int[10010];
+        int[] nonSelect = new int[10010];
+
+        int maxV = 0;
         for (int x : nums) {
             sums[x] += x;
+            maxV = Math.max(maxV, x);
         }
-        int[] select = new int[10010];
-        int[] nonSelect = new int[10010];
-        for (int i = 1; i <= 10000; i++) {
+
+        for (int i = 1; i <= maxV; i++) {
             select[i] = nonSelect[i - 1] + sums[i];
             nonSelect[i] = Math.max(select[i - 1], nonSelect[i - 1]);
         }
-
-        return Math.max(select[10000], nonSelect[10000]);
+        return Math.max(select[maxV], nonSelect[maxV]);
     }
 }
 ```
 
 ### **...**
-
 ```
 
 ```
diff --git a/solution/0700-0799/0740.Delete and Earn/README_EN.md b/solution/0700-0799/0740.Delete and Earn/README_EN.md
@@ -86,8 +86,24 @@ Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
 
 ## Solutions
 
-
 <!-- tabs:start -->
+Intuition: **If we take a number, we will take all of the copies of it**.
+
+First calculate the sum of each number as **sums**, and keep updating two dp arrays: **select** and **nonSelect**
+
+- sums[i] represents the sum of elements whose value is i;
+- select[i] represents the maximum sum of processing from 0 to i if the number i is selected;
+- nonSelect[i] represents the maximum sum of processing from 0 to i if the number i is not selected;
+
+Then we have the following conclusions:
+
+- If i is selected, then i-1 must not be selected;
+- If you do not choose i, then i-1 can choose or not, so we choose the larger one;
+
+```java
+select[i] = nonSelect[i-1] + sums[i];
+nonSelect[i] = Math.max(select[i-1], nonSelect[i-1]);
+```
 
 ### **Python3**
 
@@ -98,7 +114,29 @@ Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
 ### **Java**
 
 ```java
-
+class Solution {
+    public int deleteAndEarn(int[] nums) {
+        if (nums.length == 0) {
+            return 0;
+        }
+
+        int[] sums = new int[10010];
+        int[] select = new int[10010];
+        int[] nonSelect = new int[10010];
+
+        int maxV = 0;
+        for (int x : nums) {
+            sums[x] += x;
+            maxV = Math.max(maxV, x);
+        }
+
+        for (int i = 1; i <= maxV; i++) {
+            select[i] = nonSelect[i - 1] + sums[i];
+            nonSelect[i] = Math.max(select[i - 1], nonSelect[i - 1]);
+        }
+        return Math.max(select[maxV], nonSelect[maxV]);
+    }
+}
 ```
 
 ### **...**
diff --git a/solution/0700-0799/0740.Delete and Earn/Solution.java b/solution/0700-0799/0740.Delete and Earn/Solution.java
@@ -0,0 +1,23 @@
+public class Solution {
+    public int deleteAndEarn(int[] nums) {
+        if (nums.length == 0) {
+            return 0;
+        }
+
+        int[] sums = new int[10010];
+        int[] select = new int[10010];
+        int[] nonSelect = new int[10010];
+
+        int maxV = 0;
+        for (int x : nums) {
+            sums[x] += x;
+            maxV = Math.max(maxV, x);
+        }
+
+        for (int i = 1; i <= maxV; i++) {
+            select[i] = nonSelect[i - 1] + sums[i];
+            nonSelect[i] = Math.max(select[i - 1], nonSelect[i - 1]);
+        }
+        return Math.max(select[maxV], nonSelect[maxV]);
+    }
+}
