# Untitled

unknown
plain_text
17 days ago
1.6 kB
5
Indexable
Never
class Solution {
public:
long long maximumTotalDamage(vector<int>& power)
{
long long n = power.size();
map<long long, long long> m;
set<int> s;
sort(power.begin(), power.end());
for(int i=0; i<n;i++)
{
m[power[i]]++;
s.insert(power[i]);
}
int n1 = s.size();
long long dp[n1+1][2];
for(int i=0;i<=n1;i++)
{
for(int j=0;j<2;j++)
{
dp[i][j] = 0;
}
}
vector<long long> values;
values.push_back(0);
for(auto x: s)
{
values.push_back(x);
}
dp[1][0]=0;
auto it = s.begin();
dp[1][1] = m[values[1]]*values[1];
for(int k=2;k<=n1;k++)
{
dp[k][0] = max(dp[k-1][0],dp[k-1][1]);
if(values[k] - values[k-1] > 2)
{
int val = values[k]*m[values[k]];
dp[k][1] = max(dp[k-1][0] + val ,dp[k-1][1] + val);
}
else
{
if(values[k] - values[k-1]==2)
{
int val = values[k]*m[values[k]];
dp[k][1] = dp[k-1][0] + val;
}
else if (values[k] - values[k-1]==1)
{
int val = values[k]*m[values[k]];
if(k>2 && values[k] - values[k-2]==2)
{
dp[k][1] = dp[k-2][0] + val;
}
else
{
dp[k][1] = dp[k-1][0] + val;
}
}
}
}
return max(dp[n1][0], dp[n1][1]);
}
};