删除并获得点数

贪心地「每次选当前最大的」会出错：选大数可能丢掉两边一堆小数。这种「选了就排斥邻居」的味道，得换个角度看。

选值 v，能拿的分 = v × 它出现的次数。我们先扫一遍原数组，把「有几个」一次性折叠进 total[v]。下面看着它一格一格累出来。

第一步 · 扫原数组统计 total：下面这排是原数组。指针从最左往右走，每碰到一个数 v，就把它的得分 v 加到右边 total[v] 上。盯住右边累计值怎么涨。

扫到 nums[0] = 2：第一个数是 2，把 2 加进 total[2]，它从 0 变 2。指针继续右移。

扫到 nums[1] = 2：又是一个 2，total[2] 再加 2 变成 4——这就是「两个 2 一起拿 = 4 分」被折叠进了一格。

扫到 nums[2] = 3：轮到第一个 3，给 total[3] 加 3。值 2 那两格已经扫完(变灰)。

扫到 nums[3] = 3：第二个 3，total[3] 涨到 6。三个 3 还差最后一个。

扫到 nums[4] = 3：第三个 3 加完，total[3] 到 9——选值 3 一次性能拿 9 分。

扫到 nums[5] = 4：数到 4，给 total[4] 加 4。它紧挨着 3，选 3 就会把它清掉。

扫到 nums[6] = 6：第一个 6 入账，total[6] 变 6。注意 6 和前面的 4 之间隔着个 5，互不相邻。

扫到 nums[7] = 6：最后一个 6 加完，total[6] 到 12——两个 6 折成一格 12 分。整个数组扫完，统计阶段结束。

把值域 0~6 排成一排，每格放它的 total[v]。选一个格子就不能选它左右紧挨着的格子——这完全等价于打家劫舍(不能偷相邻两家)！

值域排成一排：把刚统计的 total 摆成柱子：下标 0~6 就是值，柱高就是 total[v]。值 5 没出现(柱高 0)，它把 4 和 6 隔开，于是选 3 又选 6 互不冲突。开始填表。

dp[v] 表示「只考虑值 0..v 时能拿的最大分」。要么不选 v(继承 dp[v-1])，要么选 v(拿 total[v]，但只能接 dp[v-2])。两者取大。

建表 · dp 行待填：上一行是 total，下一行是要填的 dp。dp[v] 的含义：只在值 0..v 里挑、且不挑相邻值，能拿的最大分。

地基 · 填 dp[0]：只有值 0 可选时，最大分就是它自己的 total[0]=0(本例没有 0)。这是不依赖别人的地基，第一格填好。

地基 · 填 dp[1]：考虑值 0、1：要么不选 1(拿 dp[0]=0)，要么选 1(拿 total[1]=0)。两者都是 0，dp[1]=0。第二格填好。

填 dp[2] · 第一次真选择：到值 2：不选继承相邻的 dp[1]=0；选就拿 total[2]=4，但不能接相邻 dp[1]，只能接隔开的 dp[0]=0 → 得 4。取大，dp[2]=4。

填 dp[3] · 关键一格：到值 3：不选继承 dp[2]=4；选拿 total[3]=9，跳过相邻 dp[2]，接 dp[1]=0 → 得 9。9 > 4，dp[3]=9。选 3 比保住 2 更划算。

填 dp[4]：到值 4：不选继承 dp[3]=9；选拿 total[4]=4，接 dp[2]=4 → 共 8。9 > 8，dp[4]=9——选 4 反而因放弃 3 而变少，所以保住 3。

填 dp[5] · 空格也要填：值 5 没出现，total[5]=0。不选继承 dp[4]=9；选它拿 0、接 dp[3]=9，也是 9。dp[5]=9 保持不变——但这一格很重要，它把 4 和 6 隔开，让 6 能接到含 3 的状态。

填 dp[6] · 最后一格：到值 6：不选继承 dp[5]=9；选拿 total[6]=12，跳过相邻 dp[5]，接 dp[4]=9(里头含了选 3 的 9 分)→ 共 21。21 > 9，dp[6]=21。这就是「选 3 又选 6」被表达了出来。

填表完成：dp 这一行滚到最后一格 dp[6]=21 就是答案。对应方案：选值 3(9 分)+ 选值 6(12 分)，它们隔得远不冲突。和示例答案 21 对上了。

先一遍统计 total，再一遍线性填 dp，每格只看前两格，整体线性，比指数枚举快到天上去。

约束是「选了 v 不能选 v±1」，冲突发生在数值相邻上，跟它们在原数组的位置无关。所以把值排成一排来 DP，先排序去重也行。

雷区实演 · 接错相邻格：如果选值 3 时去接相邻的 dp[2]=4，算出 13——可这相当于同时拿了值 2 和值 3，而它们相邻、本该互斥。正确写法是接 dp[v-2]，跳过相邻那格。

边界三连：注意「全相同」不是相邻冲突——3 和 3 是同一个值，选它就把所有 3 一起拿了，反而该全要。

面试追问：把「它就是打家劫舍」一句话讲透，再补一句值域过大时的排序变体，是这题的加分点。