求解答一道算法题

[codechaser]

/**

• 给定一个数组及其长度 n，每次在这 n 个数字中选取一个数 x，
• 然后取出数组中值为 x 的所有数，获得的资源是 x*值为 x 的元素个数；
• 同时删去刚好值小于(就是刚好比他小))和大于 x(刚好比他大一点)的所有数；
• 然后开始下一轮，直到数组为空。请问能获得的最大资源是？ */

求问这道题怎么做？

[layorlayor]

对于一个数 x, 它有 cx 个。比他小的最大数是 y，有 cy 个。比他大的最小数是 z,有 cz 个。 那是不是按照 x * cx - y * cy - z * cz 降序，然后一个一个挑？

[brainfxxk]

@no1xsyzy 个数为什么没限制，每次操作会删掉 3 个元素呀。

[no1xsyzy]

@brainfxxk 不一定，如果删的是两头的只会删掉两个，如果最后只剩一个只会删掉一个

[brainfxxk]

@no1xsyzy 啊是的，也就是如果删除的元素不一定需要有前驱和后继，那么总长度也不需要满足 3 的倍数了。

[BiteTheDust]

首先可以发现原序列没有用
我们把每个值来排序 然后根据每个值的出现次数 使得这个值获得一个权值 得到一个新的序列
显然对于这个新序列 我们不能连续地去取里面的值(也就是说我们取了某个数 就不能取相邻的数)
这样转化后我们就可以用动态规划来获得最大的总和 如果值域不大复杂度可以达到 O(n) 否则复杂度瓶颈为 nlogn 的排序

[nvioue]

不知所云 上 leetcode 链接吧 求你了

[codechaser]

@nvioue 题目的意思就是给出一个数组，你每次可以选择一个值 x，先删除数组中值为 x 的所有元素，用被删除元素个数 n_x 乘以 x 当做这次拿到的资源值，然后删去数组中正好比 x 大和 x 小的所有元素（如[2,4,4,1,5,3,6,3]，x 选 6 的话，总共要删去 6,4,4 这几个元素，资源值为 6。）这样算一次操作，若干次操作后数组会空，问加在一起最大能拿到多少资源值？我不知道这个 leetcode 上有不，这是笔试题，当时就随手记了一下。

[no1xsyzy]

@nvioue 简单地说：
Given X: uint[], n = len(X)
Require x in X while len(X) > 0
Do
X.remove(x)
X.remove(min(a for a in X if a > x))
X.remove(max(a for a in X if a < x))