You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:
nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.Return the maximum number of points you can earn by applying the above operation some number of times.
Example 1:
Input: nums = [3,4,2] Output: 6 Explanation: You can perform the following operations: - Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2]. - Delete 2 to earn 2 points. nums = []. You earn a total of 6 points.
Example 2:
Input: nums = [2,2,3,3,3,4] Output: 9 Explanation: You can perform the following operations: - Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3]. - Delete a 3 again to earn 3 points. nums = [3]. - Delete a 3 once more to earn 3 points. nums = []. You earn a total of 9 points.
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104This approach is based on converting the problem into another known dynamic programming problem, similar to the 'House Robber' problem. The idea is to first calculate the total points for each number by multiplying its value by its frequency in the array. This allows us to transform the problem into finding the optimal way to select values in a linear array where selecting one value prevents selecting its direct neighbors.
This Python solution starts by identifying the maximum number in the array to establish the range of a new points array. It increments each position in the points array by the value times its occurrence. We then iterate over this points array, applying a dynamic programming strategy similar to solving 'House Robber', determining for each value whether taking it or skipping it yields more points.
C++
Time Complexity: O(n + m) where n is the number of elements in nums and m is the maximum number in nums.
Space Complexity: O(m) used by the points array.
This approach uses a map to store the points for each number, avoiding the space usage related to the maximum number in the points array and processing only numbers that exist in the input. We can still utilize a dynamic programming strategy to compute maximum points.
In this Java solution, we map each number to its accumulated points. This avoids predefined array size based on max number and allows compact representation for sparse input. We then iterate over the map and use dynamic programming to find the maximum points.
JavaScript
Time Complexity: O(n + k) where n is the number of elements and k is the number of unique elements in nums.
Space Complexity: O(k) for storing elements in map.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Points Array | Time Complexity: O(n + m) where n is the number of elements in nums and m is the maximum number in nums. |
| Dynamic Programming with Map | Time Complexity: O(n + k) where n is the number of elements and k is the number of unique elements in nums. |
Delete and Earn - Dynamic Programming - Leetcode 740 - Python • NeetCode • 56,231 views views
Watch 9 more video solutions →Practice Delete and Earn with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor