---
tags: leetcode
---

# [740. Delete and Earn](https://leetcode.com/problems/delete-and-earn/)
---
# My Solution
## Solution 1: Brute force (TLE)
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    int deleteAndEarn(vector<int> &nums) {
        // Find the maximum number in nums.
        int maxNum = 0;
        for (auto &num : nums) {
            if (maxNum < num) {
                maxNum = num;
            }
        }
        
        // We want to sort nums but we don't use sorting algorithm.
        
        // We use another array, values, to accumulate the all the 
        // numbers in nums. For example, if nums = [2,2,3,3,3,4], 
        // values will be [0,0,4,9,4]. 
        // Therefore, values[nums[i]] = nums[i] * n, for n is the 
        // number of occurences of nums[i].
        // Because the 1 <= nums[0] <= 10^4, values[0] is always zero.
        vector<int> values(maxNum + 1, 0);
        for (auto &num : nums) {
            values[num] += num;
        }
        
        return getMaxPoints(values, values.size() - 1);
    }
    
private:
    // getMaxPoints returns the maximum points from values[1..i].
    int getMaxPoints(vector<int> &values, int i) {
        if (i == 0) {
            // base case 1:
            // Because 0 is not valid in nums, it gains zero points.
            return values[0];
        }
        
        if (i == 1) {
            // base case 2: 
            // Because 1 is the smallest valid number in nums, the 
            // maximum points we can get is values[1].
            return values[1];
        }
        
        return max(getMaxPoints(values, i - 1), getMaxPoints(values, i - 2) + values[i]);
    }
};

### Time Complexity
$O(n + 2^{maxNum})$
$n$ is the length of `nums`.
$maxNum$ is the maximum number in `nums`.
### Space Complexity
$O(maxNum)$
## Solution 2: Top-down DP
### The Key Idea for Solving This Coding Question
### C++ Code 1

class Solution {
public:
    int deleteAndEarn(vector<int> &nums) {
        // Find the maximum number in nums.
        int maxNum = 0;
        for (auto &num : nums) {
            if (maxNum < num) {
                maxNum = num;
            }
        }
        
        // We want to sort nums but we don't use sorting algorithm.
        
        // We use another array, values, to accumulate the all the 
        // numbers in nums. For example, if nums = [2,2,3,3,3,4], 
        // values will be [0,0,4,9,4]. 
        // Therefore, values[nums[i]] = nums[i] * n, for n is the 
        // number of occurences of nums[i].
        // Because the 1 <= nums[0] <= 10^4, values[0] is always zero.
        vector<int> values(maxNum + 1, 0);
        for (auto &num : nums) {
            values[num] += num;
        }
        
        // memo[i] is the maximum points we can get from nums[1..i].
        unordered_map<int, int> memo;
        
        // Base case 1:
        // 0 is not a valid number in numbers, we can get 0 point.
        memo[0] = 0;
        
        // Base case 2:
        // 1 is the smallest valid number in nums. If there are only 1
        // in nums, values[1] is the maximum points.
        memo[1] = values[1];
        
        return getMaxPoints(values, memo, values.size() - 1);
    }
    
private:
    // getMaxPoints returns the maximum points from values[1..i].
    int getMaxPoints(vector<int> &values, unordered_map<int, int> &memo, int i) {
        auto iter = memo.find(i);
        if (iter != memo.end()) {
            return iter->second;
        }
        
        return memo[i] = max(getMaxPoints(values, memo, i - 1), 
                             getMaxPoints(values, memo, i - 2) + values[i]);
    }
};

### C++ Code 2

class Solution {
public:
    int deleteAndEarn(vector<int> &nums) {
        // Find the maximum number in nums.
        int maxNum = 0;
        for (auto &num : nums) {
            if (maxNum < num) {
                maxNum = num;
            }
        }
        
        // We want to sort nums but we don't use sorting algorithm.
        
        // We use another array, values, to accumulate the all the 
        // numbers in nums. For example, if nums = [2,2,3,3,3,4], 
        // values will be [0,0,4,9,4]. 
        // Therefore, values[nums[i]] = nums[i] * n, for n is the 
        // number of occurences of nums[i].
        // Because the 1 <= nums[0] <= 10^4, values[0] is always zero.
        vector<int> values(maxNum + 1, 0);
        for (auto &num : nums) {
            values[num] += num;
        }
        
        // memo[i] is the maximum points we can get from nums[1..i].
        vector<int> memo(maxNum + 1, -1);
        
        // Base case 1:
        // 0 is not a valid number in numbers, we can get 0 point.
        memo[0] = 0;
        
        // Base case 2:
        // 1 is the smallest valid number in nums. If there are only 1
        // in nums, values[1] is the maximum points.
        memo[1] = values[1];
        
        return getMaxPoints(values, memo, values.size() - 1);
    }
    
private:
    // getMaxPoints returns the maximum points from values[1..i].
    int getMaxPoints(vector<int> &values, vector<int> &memo, int i) {
        if (memo[i] >= 0) {
            return memo[i];
        }
        
        return memo[i] = max(getMaxPoints(values, memo, i - 1), 
                             getMaxPoints(values, memo, i - 2) + values[i]);
    }
};

### Time Complexity
$O(n + maxNum)$
$n$ is the length of `nums`.
$maxNum$ is the maximum number in `nums`.
### Space Complexity
$O(maxNum)$
## Solution 3: Buttom-up DP
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    int deleteAndEarn(vector<int> &nums) {
        // Find the maximum number in nums.
        int maxNum = 0;
        for (auto &num : nums) {
            if (maxNum < num) {
                maxNum = num;
            }
        }
        
        // We want to sort nums but we don't use sorting algorithm.
        
        // We use another array, values, to accumulate the all the 
        // numbers in nums. For example, if nums = [2,2,3,3,3,4], 
        // values will be [0,0,4,9,4]. 
        // Therefore, values[nums[i]] = nums[i] * n, for n is the 
        // number of occurences of nums[i].
        // Because the 1 <= nums[0] <= 10^4, values[0] is always zero.
        vector<int> values(maxNum + 1, 0);
        for (auto &num : nums) {
            values[num] += num;
        }
        
        // dp[i] is the maximum points we can get from nums[1..i].
        vector<int> dp(maxNum + 1, -1);
        
        // Base case 1:
        // 0 is not a valid number in numbers, we can get 0 point.
        dp[0] = 0;
        
        // Base case 2:
        // 1 is the smallest valid number in nums. If there are only 1
        // in nums, values[1] is the maximum points.
        dp[1] = values[1];
        
        for (int i = 2; i <= maxNum; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + values[i]);
        }
        
        return dp[maxNum];
    }
};

### Time Complexity
$O(n + maxNum)$
$n$ is the length of `nums`.
$maxNum$ is the maximum number in `nums`.
### Space Complexity
$O(maxNum)$
## Solution 4: Buttom-up DP (no DP array)
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    int deleteAndEarn(vector<int> &nums) {
        // Find the maximum number in nums.
        int maxNum = 0;
        for (auto &num : nums) {
            if (maxNum < num) {
                maxNum = num;
            }
        }
        
        // We want to sort nums but we don't use sorting algorithm.
        
        // We use another array, values, to accumulate the all the 
        // numbers in nums. For example, if nums = [2,2,3,3,3,4], 
        // values will be [0,0,4,9,4]. 
        // Therefore, values[nums[i]] = nums[i] * n, for n is the 
        // number of occurences of nums[i].
        // Because the 1 <= nums[0] <= 10^4, values[0] is always zero.
        vector<int> values(maxNum + 1, 0);
        for (auto &num : nums) {
            values[num] += num;
        }
        
        // Base case 1:
        // 0 is not a valid number in numbers, we can get 0 point.
        int dp0 = 0;
        
        // Base case 2:
        // 1 is the smallest valid number in nums. If there are only 1
        // in nums, values[1] is the maximum points.
        int dp1 = values[1];
        
        int dp2 = max(dp0, dp1);
        for (int i = 2; i <= maxNum; ++i) {
            dp2 = max(dp1, dp0 + values[i]);
            dp0 = dp1;
            dp1 = dp2;
        }
        
        return dp2;
    }
};

### Time Complexity
$O(n + maxNum)$
$n$ is the length of `nums`.
$maxNum$ is the maximum number in `nums`.
### Space Complexity
$O(maxNum)$
# Miscellaneous
<!--
# Test Cases

[3,4,2]

[2,2,3,3,3,4]

[1]

[5,3,2,4,5,6,7,2,2,1,10000]

* Time Limit Error:

[12,32,93,17,100,72,40,71,37,92,58,34,29,78,11,84,77,90,92,35,12,5,27,92,91,23,65,91,85,14,42,28,80,85,38,71,62,82,66,3,33,33,55,60,48,78,63,11,20,51,78,42,37,21,100,13,60,57,91,53,49,15,45,19,51,2,96,22,32,2,46,62,58,11,29,6,74,38,70,97,4,22,76,19,1,90,63,55,64,44,90,51,36,16,65,95,64,59,53,93]

-->