This is broken. My output equals the expected output, and it still says I fail. There is only one correct answer, you should not fail people for providing it.
Do you have extra space in the output?
The “Slight Optimization” solution is incorrect. It gives indexOutOfBound error for all test cases. Please check your answer.
This works
public static int maxScoreV2(List<Integer> coins, List<Integer> prefixSum, int l, int r) {
if (l == r) {
return coins.get(r-1);
}
int sum = prefixSum.get(r) - prefixSum.get(l-1);
int leftPick = maxScoreV2(coins, prefixSum, l + 1, r);
int rightPick = maxScoreV2(coins, prefixSum, l, r - 1);
return sum - Math.min(leftPick, rightPick);
}
public static int coinGameV2(List<Integer> coins) {
int n = coins.size();
List<Integer> prefixSum = new ArrayList<>(); // precompute prefix sums
prefixSum.add(0);
for (int i = 1; i <= n; i++) {
prefixSum.add(prefixSum.get(i - 1) + coins.get(i - 1));
}
return maxScoreV2(coins, prefixSum, 1, n);
}