10:I[13699,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 11:I[25152,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 12:T463,class Solution { int[][] memo; public int stoneGameV(int[] stoneValue) { int n = stoneValue.length; memo = new int[n][n]; int[] prefixSum = new int[n + 1]; for (int i = 0; i < n; i++) prefixSum[i + 1] = prefixSum[i] + stoneValue[i]; return dfs(stoneValue, 0, n - 1, prefixSum); } private int dfs(int[] stoneValue, int left, int right, int[] prefixSum) { if (left == right) return 0; if (memo[left][right] != 0) return memo[left][right]; int ans = 0; for (int i = left; i < right; i++) { int leftSum = prefixSum[i + 1] - prefixSum[left]; int rightSum = prefixSum[right + 1] - prefixSum[i + 1]; if (leftSum < rightSum) ans = Math.max(ans, leftSum + dfs(stoneValue, left, i, prefixSum)); else if (leftSum > rightSum) ans = Math.max(ans, rightSum + dfs(stoneValue, i + 1, right, prefixSum)); else ans = Math.max(ans, leftSum + Math.max(dfs(stoneValue, left, i, prefixSum), dfs(stoneValue, i + 1, right, prefixSum))); } return memo[left][right] = ans; } }13:T41b,class Solution { public: int stoneGameV(vector& stoneValue) { int n = stoneValue.size(); vector> memo(n, vector(n, 0)); vector prefixSum(n + 1, 0); for (int i = 0; i < n; i++) prefixSum[i + 1] = prefixSum[i] + stoneValue[i]; function dfs = [&](int left, int right) { if (left == right) return 0; if (memo[left][right] != 0) return memo[left][right]; int ans = 0; for (int i = left; i < right; i++) { int leftSum = prefixSum[i + 1] - prefixSum[left]; int rightSum = prefixSum[right + 1] - prefixSum[i + 1]; if (leftSum < rightSum) ans = max(ans, leftSum + dfs(left, i)); else if (leftSum > rightSum) ans = max(ans, rightSum + dfs(i + 1, right)); else ans = max({ans, leftSum + dfs(left, i), leftSum + dfs(i + 1, right)}); } return memo[left][right] = ans; }; return dfs(0, n - 1); } };

Time Complexity

Space Complexity