UVa 10891

this is an extention of a classic dp game problem sum of a subsequnce can be represented by 1-d or 2-d array
state:
    dp[i][j] - max difference of subsequnce i to j
    the DAG here is (i+1, j), (i, j-1) -> (i, j)
    this tells us the iteration order of states for j=1 to n-1, for i=0 to i+j
transtion:
    dp[i][j]=max(dp[i][j], s[i][j]-dp[p][q]), i+1<=p<=j, i<=q<j

/* UVas */
/*****************************************************************************/
int n;
int a[100];
int s[101];
int d[100][100];
int main(void) {
    while (cin>>n&&n) {
        for (int i=0; i<n; i++) {
            cin>>a[i];
            s[i+1]=s[i]+a[i];
        }
        memset(d, 0, sizeof(d));
        for (int i=0; i<n; i++) {
            d[i][i]=a[i];
        }
        for(int j=1; j<n; j++){
            for(int i=0; i+j<n; i++){
                int m=0;
                for(int k=i+1; k<=i+j; k++) {
                    m=min(m, d[k][i+j]);
                }
                for(int k=i; k<i+j; k++) {
                    m=min(m, d[i][k]);
                }
                d[i][i+j]=s[i+j+1]-s[i]-m;
            }
        }
        cout<<2*d[0][n-1]-s[n]<<endl;
    }
    return 0;
}
/*****************************************************************************/