Sponsored
Sponsored
This 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.
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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int deleteAndEarn(vector<int>& nums) {
6 int maxNum = *max_element(nums.begin(), nums.end());
7 vector<int> points(maxNum + 1, 0);
8 for (int num : nums) {
9 points[num] += num;
10 }
11
12 int take = 0, skip = 0;
13 for (int point : points) {
14 int take_i = skip + point;
15 int skip_i = max(take, skip);
16 take = take_i;
17 skip = skip_i;
18 }
19 return max(take, skip);
20}The C++ solution mirrors the Python approach. It first computes the points array by calculating the sums of all values multiplied by their counts, then iteratively decides to take or skip each value to maximize points.
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.
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.
1import java.util.Map;
2import
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.