Ruby: prefix sum and recursion
Code\nruby\nclass Array\n  def scan(st) = map { st = yield st, _1 }\n  def prefsum = scan(0, &:+).unshift(0)\nend\n\ndef max_value_of_coins(piles, k)\n  @pile_p
# Code\n```ruby\nclass Array\n  def scan(st) = map { st = yield st, _1 }\n  def prefsum = scan(0, &:+).unshift(0)\nend\n\ndef max_value_of_coins(piles, k)\n  @pile_prefs = piles.map(&:prefsum)\n  @size_prefs = piles.map(&:size).prefsum\n  @_dp = Array.new(piles.size) { [] } << -> _ { 0 }\n  dp(0, k)\nend\n\ndef dp(i, k)\n  @_dp[i][k] ||= begin\n    pref = @pile_prefs[i]\n    rem = @size_prefs[-1] - @size_prefs[i + 1]\n    (max(0, k - rem)..min(k, pref.size - 1)).map { pref[_1] + dp(i + 1, k - _1) }.max\n  end\nend\n\ndef min(a, b) = a < b ? a : b\ndef max(a, b) = a > b ? a : b\n```\n\n# Time complexity\n\n$$\\mathcal{O}(\\sum|\\text{piles}_i|)$$\n\n# Space complexity\n\n$$\\mathcal{O}(\\sum|\\text{piles}_i|)$$
['Recursion', 'Prefix Sum', 'Ruby']