Delete and Earn LeetCode solution in C++

1
class Solution {
2
 public:
3
  // Dynamic Programming : Bottom Up Approach Optmised
4
  int deleteAndEarn(vector<int> &nums) {
5
    int size = nums.size();
6

7
    // Initialise vectors with size 10001 and value 0
8
    vector<int> memo(10001, 0);
9
    vector<int> res(10001, 0);
10

11
    // get the count of elements int res vector
12
    for (auto num : nums) res[num]++;
13

14
    // for index : less than 3 calculate memo[i] as the index times number of
15
    // occurences : greater than equal to 3 as calculate memo[i] as the index
16
    // times number of occurences + max of the last second and third element
17
    for (int i = 0; i < 10001; i++)
18
      memo[i] += (i < 3) ? (i * res[i]) : (i * res[i]) + max(memo[i - 2], memo[i - 3]);
19

20
    // return max of last 2 elements
21
    return max(memo[10000], memo[9999]);
22
  }
23
};