Skip to content

Instantly share code, notes, and snippets.

@kanrourou
Created May 10, 2018 04:43
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
if (nums.empty())return 0;
map<int, int> cnts;
for (const auto& num : nums)++cnts[num];
vector<vector<int>> dp(cnts.size(), vector<int>(2, INT_MAX));
auto iter = cnts.begin();
dp[0][0] = 0;
dp[0][1] = cnts[iter->first] * iter->first;
int n = cnts.size(), prev = iter->first;
++iter;
for(int i = 1; i < n; ++i, ++iter)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = iter->first - prev == 1 ? cnts[iter->first] * iter->first + dp[i - 1][0] : cnts[iter->first] * iter->first + max(dp[i - 1][0], dp[i - 1][1]);
prev = iter->first;
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment