---
# System prepended metadata

title: Leetcode 740. Delete and Earn
tags: [Leetcode(C++)]

---

# Leetcode 740. Delete and Earn
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/delete-and-earn/ 。

想法 : 

    陣列代表 : 到目前為止的最大元素和。
    如果不選這個數字 => 最大值=它-1。
    選了的話就是它-2+它自己。

時間複雜度 : 

程式碼 :

```
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int ans[10010]={0},num[10010]={0},l=nums.size(),maxn=0,mini=10010;
        for(int i=0 ; i<l ; i++){
            num[nums[i]]++;
            maxn=max(maxn,nums[i]);
            mini=min(mini,nums[i]);
        }
        
        for(int i=mini ; i<=maxn ; i++){
            ans[i]+=i*num[i];
            cout << ans[i] << endl;
        }
        
        for(int i=mini ; i<=maxn ; i++){
            if(i == 1) continue;
            ans[i]=max(ans[i-1],ans[i-2]+ans[i]);
        }
        
        return ans[maxn];
    }
};
```