题目如下

数据范围

  本题和打家劫舍类似都是取和不取两种情况：令f(i)为从0到i可以打出的最高伤害1.当选择不取第i个数那么直接选取f(i - 1)即可2.当选择选取第i个数时 我们要选择离 power[i] - 2 最近的下标j从0到j选取即f(j) + power[i]  *   power[i]个数即可 例如 [1 2 3 4 5]当i = 3时最近的j是0。

通过代码

class Solution {
public:long long maximumTotalDamage(vector<int>& power) {long long ans = 0;vector<int> nums;int n = power.size();unordered_map<int,int> map;for(int i = 0;i < n;i++){if(map.count(power[i]) == 0)nums.push_back(power[i]);map[power[i]]++;}sort(nums.begin(),nums.end());n = nums.size();vector<vector<long long>> v(n,vector<long long>(2,0));v[0][1] = 1l * nums[0] * map[nums[0]];for(int i = 1,j = 0;i < n;i++){v[i][0] = max(v[i - 1][0],v[i - 1][1]);for(j = i;j >= 0;j--){if(nums[j] < nums[i] - 2)break;}if(j == -1){v[i][1] = nums[i] * map[nums[i]];}else{v[i][1] = max(v[j][0],v[j][1]) + nums[i] * map[nums[i]];}}return max(v[n - 1][0],v[n - 1][1]);}
};