Concise C++ code. Sort and O(1) extra space


  • 0
    F

    Final optimized version, O(N)+O(1) space

    int deleteAndEarn(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        sort(nums.begin(), nums.end());
        int earnInclusion = nums[0];
        int earnExclusion = 0;
    
        for(int i=1; i < nums.size(); ++i) {
            int lastMax = max(earnInclusion, earnExclusion);
            if(nums[i] > nums[i-1] + 1) {
                earnInclusion = lastMax + nums[i];
                earnExclusion = lastMax;
            }else if(nums[i] == nums[i-1]) {
                earnInclusion = earnInclusion + nums[i];
            }else {
                earnInclusion = earnExclusion + nums[i];
                earnExclusion = lastMax;
            }
        }
        return max(earnInclusion, earnExclusion);
    }
    

    DP with two arrays:

    int deleteAndEarn(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> earnInclusion(nums.size(), 0);
        vector<int> earnExclusion(nums.size(), 0);
        if(nums.size() == 0) return 0;
        earnInclusion[0] = nums[0];
        int lastMax;
        for(int i=1; i < nums.size(); ++i) {
            lastMax = max(earnInclusion[i-1], earnExclusion[i-1]);
            if(nums[i] > nums[i-1] + 1) {
                earnInclusion[i] = lastMax + nums[i];
                earnExclusion[i] = lastMax;
            }else if(nums[i] == nums[i-1]) {
                earnInclusion[i] = earnInclusion[i-1] + nums[i];
                earnExclusion[i] = earnExclusion[i-1];
            }else {
                earnInclusion[i] = earnExclusion[i-1] + nums[i];
                earnExclusion[i] = lastMax;
            }
        }
        return max(earnInclusion[nums.size()-1], earnExclusion[nums.size()-1]);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.