Interval Dynamic Programming | Coin Game - Dynamic Programming / Interval

https://algo.monster/problems/coin_game

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);        
}

posted the problem and the fix at https://github.com/realAlgoMonster/contrib/issues/67

This reminds me https://leetcode.com/problems/stone-game/