Untitled

mail@pastecode.io avatar
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]);
    }
};
Leave a Comment