UVa 10891 - Game of Sum

// UVa 10891 - Game of Sum

#include <iostream>
#include <string.h>
using namespace std;

#define integer signed long long int

integer oo[1];

int main() {
	memset(oo, 127, sizeof(oo));
	int n;
	while (cin >> n && n) {
		// input
		integer s[101];
		s[0] = 0;
		for (int i = 1; i <= n; i++) {
			cin >> s[i];
			s[i] += s[i - 1];
		}
		// DP
		integer T[102][102];
		memset(T, 0, sizeof(T));
		for (int d = 0; d < n; d++) {
			for (int i = 1; i <= n - d; i++) {
				int j = i + d;
				integer best = -oo[0];
				for (int k = i; k <= j; k++) {
					// take from i to k
					if (s[k] - s[i - 1] - T[k + 1][j] > best)
						best = s[k] - s[i - 1] - T[k + 1][j];
					// take from k to j
					if (s[j] - s[k - 1] - T[i][k - 1] > best)
						best = s[j] - s[k - 1] - T[i][k - 1];
				}
				T[i][j] = best;
			}
		}

		cout << T[1][n] << endl;

	}
	return 0;
}