首先假若在某一次取数中最小的数是 $x$，那实际上你就可以吧大于等于 $x$ 的数全部取走，反正得分没变而且使得对手可以取的方案变劣了，所以一定是不劣的。

也就是说所每次取完数剩下的一定是小于等于 $x$ 的所有数，不放先把所有数排序，然后设计状态 $dp_i$ 表示取后把前 $i$ 个数取完的最大答案，显然有转移 $dp_i = \max(a_{j+1} - dp_{j})$。直接记录 $\max(a_{i+1} - dp_i)$ 然后 $O(n)$ 转移即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6+114;
int n,a[maxn],dp[maxn];
set<int> S;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        S.insert(a[i]);
    }
    int tot=0;
    for(int x:S) a[++tot]=x;
    //容易发现最优情况下每次都是选择一个数并且把比这个数大的数全部取掉
    //所以设计状态 dp[i] 表示取完除了前 i 大以外的数的答案
    //dp[i] = max(a[j+1]-dp[j])
    int mx=a[1],dp=0;
    for(int i=1;i<=tot;i++){
        dp=mx;
        mx=max(mx,a[i+1]-dp);
    }
    cout<<dp<<'\n';
    return 0;
}