package com.fishercoder.solutions;

public class _740 {
    public static class Solution1 {
        /**
         * Since the number is within range [1, 10000], we can build another array:
         * each number in the array denotes the total sum of this number that appears in this array
         * and
         * use the numbers themselves in the indices of another array
         * <p>
         * credit: https://leetcode.com/problems/delete-and-earn/discuss/109895/JavaC++-Clean-Code-with-Explanation
         * <p>
         * In essence, this is the same as House Robber: https://leetcode.com/problems/house-robber/
         */
        public int deleteAndEarn(int[] nums) {
            int n = 10001;
            int[] values = new int[n];
            for (int num : nums) {
                values[num] += num;
            }

            int take = 0;
            int skip = 0;
            for (int i = 0; i < n; i++) {
                int takeI = skip + values[i];
                int skipI = Math.max(skip, take);
                take = takeI;
                skip = skipI;
            }
            return Math.max(take, skip);
        }
    }
}

@@ -29,16 +29,43 @@
 tions;%0A%0A
+import java.util.TreeMap;%0A%0A
 public c
@@ -549,16 +549,37 @@
        *
+ Notes:%0A         * 1.
  In esse
@@ -661,16 +661,162 @@
 robber/%0A
+         * 2. We are adding the number itself into values, instead of its frequency because we will directly use this value to compute the result%0A
         
@@ -1278,24 +1278,24 @@
           %7D%0A
-
             
@@ -1338,11 +1338,947 @@
  %7D%0A    %7D
+%0A%0A    public static class Solution2 %7B%0A        /**%0A         * A simplified version using treemap instead of an array, credit: https://leetcode.com/problems/delete-and-earn/discuss/109895/JavaC++-Clean-Code-with-Explanation/111626%0A         */%0A        public int deleteAndEarn(int%5B%5D nums) %7B%0A            TreeMap%3CInteger, Integer%3E treeMap = new TreeMap%3C%3E();%0A            for (int num : nums) %7B%0A                treeMap.put(num, treeMap.getOrDefault(num, 0) + num);%0A            %7D%0A            int prev = 0;%0A            int curr = 0;%0A            for (int key : treeMap.keySet()) %7B%0A                if (!treeMap.containsKey(key - 1)) %7B%0A                    prev = curr;%0A                    curr += treeMap.get(key);%0A                %7D else %7B%0A                    int tmp = Math.max(prev + treeMap.get(key), curr);%0A                    prev = curr;%0A                    curr = tmp;%0A                %7D%0A            %7D%0A            return curr;%0A        %7D%0A    %7D
 %0A%7D%0A

refactor 740