心血来潮，写个记忆化搜索
#include <cstdio>
using namespace std;
int s[150005], dpadd[150005], dpsub[150005];
int dfssub(int);
int dfsadd ( int n )
{
    int i, j;
    if ( dpadd[n] != -1000000 ) return dpadd[n];
    else
    {
        i = dfssub(n-1)-s[n];
        j = dfsadd(n-1);
        dpadd[n] = i > j ? i : j;
        return dpadd[n];
    }
}
int dfssub( int n )
{
    int i, j;
    if ( dpsub[n] != -1000000 ) return dpsub[n];
    else
    {
        i = dfsadd(n-1)+s[n];
        j = dfssub(n-1);
        dpsub[n] = i > j ? i : j;
        return dpsub[n];
    }
}
int main()
{
    int p, i, ans;
    scanf( "%d", &p );
    for ( i = 0; i < p; i++ )
    {
        scanf( "%d", &s[i] );
    }
    for ( i = 0; i < 150005; i++ )
    {
        dpadd[i] = -1000000;
        dpsub[i] = -1000000;
    }
    dpsub[0] = s[0];
    dpadd[0] = 0;
    ans = dfsadd(p-1) > dfssub(p-1) ? dfsadd(p-1) : dfssub(p-1);
    printf( "%d\n", ans );
    return 1;
}