1
class Solution {
2
  int dp[][];
3

4
  public int fnc(int a[], int i, int j, int sum) {
5
    // System.out.println(i+" "+j);
6
    int n = a.length;
7
    if (i > j) return 0;
8
    if (j > n) return 0;
9
    if (i == j) {
10
      dp[i][j] = -1;
11
      return 0;
12
    }
13
    if (dp[i][j] != 0) return dp[i][j];
14

15
    int temp = 0;
16
    int ans = Integer.MIN_VALUE;
17

18
    for (int index = i; index <= j; index++) {
19
      temp += a[index];
20
      if (temp > sum - temp) {
21
        ans = Math.max(ans, ((sum - temp) + fnc(a, index + 1, j, sum - temp)));
22
      } else if (temp < sum - temp) {
23
        ans = Math.max(ans, temp + fnc(a, i, index, temp));
24
      } else
25
        ans =
26
            Math.max(
27
                ans,
28
                Math.max(
29
                    sum - temp + fnc(a, index + 1, j, sum - temp), temp + fnc(a, i, index, temp)));
30
    }
31
    dp[i][j] = ans;
32
    return dp[i][j];
33
  }
34

35
  public int stoneGameV(int[] stoneValue) {
36
    int n = stoneValue.length;
37
    int sum = 0;
38
    for (int ele : stoneValue) sum += ele;
39
    dp = new int[n][n];
40
    return fnc(stoneValue, 0, n - 1, sum);
41
  }
42
}