Description

Submission

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int maxElement = *max_element(nums.begin(), nums.end());

        vector<int> gain(maxElement + 1, 0);
        for(int x: nums) {
            gain[x] += x;
        }

        int p = 0, q = 0;
        for(int i = 0; i <= maxElement; ++i) {
            int p2 = p, q2 = q;
            p = q2 + gain[i];
            q = max(q2, p2);
        }
        return max(p, q);
    }
};

// p[n]: the maximum value obtained taking n
// q[n]: the maximum value obtained not taking n

// p[n] = q[n-1] + gain[n];
// q[n] = max(q[n-1], p[n-1]);