# Time:  O(n)
# Space: O(1)

class Solution(object):
    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        vals = [0] * 10001
        for num in nums:
            vals[num] += num
        val_i, val_i_1 = vals[0], 0
        for i in xrange(1, len(vals)):
            val_i_1, val_i_2 = val_i, val_i_1
            val_i = max(vals[i] + val_i_2, val_i_1)
        return val_i

@@ -22,16 +22,903 @@
 : O(1)%0A%0A
+# Given an array nums of integers, you can perform operations on the array.%0A#%0A# In each operation, you pick any nums%5Bi%5D and delete it to earn nums%5Bi%5D points.%0A# After, you must delete every element equal to nums%5Bi%5D - 1 or nums%5Bi%5D + 1.%0A#%0A# You start with 0 points.%0A# Return the maximum number of points you can earn by applying such operations.%0A#%0A# Example 1:%0A# Input: nums = %5B3, 4, 2%5D%0A# Output: 6%0A# Explanation: %0A# Delete 4 to earn 4 points, consequently 3 is also deleted.%0A# Then, delete 2 to earn 2 points. 6 total points are earned.%0A#%0A# Example 2:%0A# Input: nums = %5B2, 2, 3, 3, 3, 4%5D%0A# Output: 9%0A# Explanation: %0A# Delete 3 to earn 3 points, deleting both 2's and the 4.%0A# Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.%0A# 9 total points are earned.%0A#%0A# Note:%0A# - The length of nums is at most 20000.%0A# - Each element nums%5Bi%5D is an integer in the range %5B1, 10000%5D.%0A%0A
 class So

Update delete-and-earn.py