• Source 
    1. /**************************************************************
    2.     Problem: 2091
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:892 ms
    7.     Memory:12524 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. #include<queue>
    14. //by zrt
    15. //problem:
    16. using namespace std;
    17. typedef long long ll;
    18. const double eps(1e-10);
    19. int a[1000005],n;
    20. int read(){
    21.     static char x;
    22.     static int num;
    23.     while(x=getchar(),x<'0'||x>'9');
    24.     num=x-'0';
    25.     while(x=getchar(),x>='0'&&x<='9') num*=10,num+=x-'0';
    26.     return num;
    27. }
    28. long long dp[1000005];
    29. int main(){
    30.     #ifdef LOCAL
    31.     freopen("in.txt","r",stdin);
    32.     freopen("out.txt","w",stdout);
    33.     #endif
    34.     n=read();
    35.     for(int i=1;i<=n;i++) a[i]=read();
    36.     sort(a+1,a+n+1);
    37.     for(int i=1;i<=n;i++){
    38.         dp[i]=max(a[i]-dp[i-1],dp[i-1]);
    39.     }
    40.     printf("%d\n",dp[n]);
    41.     return 0;
    42. }