LeetCode 740. Delete and Earn

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int n = nums.size();
        if (n == 1) return nums[0];
        vector<int> dp;
        sort(nums.begin(), nums.end());
        int i = 0, j, curr;
        while (i < n) {
            curr = nums[i];
            j = i + 1;
            while (j < n && nums[i] == nums[j])
                ++j;
            int curr = (j - i) * nums[i];
            if (!dp.empty()) {
                if (nums[i] != nums[i - 1] + 1)
                    curr += dp.back();
                else if (dp.size() == 1)
                    curr = max(dp.back(), curr);
                else
                    curr = max(dp.back(), curr + dp[dp.size() - 2]);
            }
            dp.emplace_back(curr);
            i = j;
        }
        return dp.back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
private:
    int rob(vector<int> &nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int a = nums[0], b = max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            int temp = b;
            b = max(a + nums[i], b);
            a = temp;
        }
        return b;
    }
public:
    int deleteAndEarn(vector<int> &nums) {
        int n = nums.size(), ans = 0;
        sort(nums.begin(), nums.end());
        vector<int> sum = {nums[0]};
        for (int i = 1; i < n; ++i) {
            int val = nums[i];
            if (val == nums[i - 1]) {
                sum.back() += val;
            } else if (val == nums[i - 1] + 1) {
                sum.push_back(val);
            } else {
                ans += rob(sum);
                sum = {val};
            }
        }
        ans += rob(sum);
        return ans;
    }
};