maxCoins function

int maxCoins(
  1. List<int> nums
)

Implementation

int maxCoins(List<int> nums) {
  if (nums.isEmpty) return 0;
  // pad with 1s at both ends
  final vals = <int>[1, ...nums, 1];
  final m = vals.length;
  final dp = List.generate(m, (_) => List<int>.filled(m, 0));

  for (var len = 2; len < m; len++) {
    for (var left = 0; left + len < m; left++) {
      final right = left + len;
      var best = 0;
      for (var k = left + 1; k < right; k++) {
        final coins =
            vals[left] * vals[k] * vals[right] + dp[left][k] + dp[k][right];
        if (coins > best) best = coins;
      }
      dp[left][right] = best;
    }
  }
  return dp[0][m - 1];
}