【Leetcode】740. Delete and Earn

题目地址：

https://leetcode.com/problems/delete-and-earn/description/

给定一个长$n$数组$A$，可以从中依次挑选若干数，如果挑了$x$，那么所有的$x-1,x+1$就都不允许挑了。问挑的数总和最大值。题目保证$A$中只有正整数。

设$f[i][0,1]$分别为只考虑$A$中$1\sim i$的数情况下，不取$i$和取$i$各自情况下能取得的数总和的最大值。由于$A$中只有正整数，那么某个数要么不取，如果取则肯定要全取。如果$i$这个数不取的话，那么$i-1$这个数可以取也可以不取，从而 f [ i ] [ 0 ] = max ⁡ { f [ i − 1 ] [ 0 ] , f [ i − 1 ] [ 1 ] } f[i][0]=\max\{f[i-1][0],f[i-1][1]\} f[i][0]=max{f[i−1][0],f[i−1][1]}；如果$i$这个数取的话，那么$i-1$必然不能取，从而$f[i][1]=i\times c[i]+f[i-1][0]$，$c[i]$表示$i$在$A$中出现的次数。代码如下：

class Solution {
 public:
  int deleteAndEarn(vector<int>& nums) {
    int M = *max_element(nums.begin(), nums.end());
    int cnt[M + 1];
    memset(cnt, 0, sizeof cnt);
    for (int x : nums) cnt[x]++;
    int f[M + 1][2];
    memset(f, 0, sizeof f);
    int res = 0;
    for (int i = 1; i <= M; i++) {
      f[i][0] = max(f[i - 1][0], f[i - 1][1]);
      f[i][1] = f[i - 1][0] + i * cnt[i];
      res = max({res, f[i][0], f[i][1]});
    }

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时空复杂度$O(\max A)$。