1
class Solution {
2
 public:
3
  int stoneGameVII(vector<int> &S) {
4
    int N = S.size();
5
    vector<int> dp(N);
6
    for (int i = N - 2; ~i; i--) {
7
      int total = S[i];
8
      for (int j = i + 1; j < N; j++) {
9
        total += S[j];
10
        dp[j] = max(total - S[i] - dp[j], total - S[j] - dp[j - 1]);
11
      }
12
    }
13
    return dp[N - 1];
14
  }
15
};