2106_max_fruits.rb

# Here is my solution, ignoring the sparse optimization, so we iterate over k. Originally, I wanted to only keep track
# of the locations with fruit.
def max_total_fruits(fruits, start_pos, k)
  steps = []

  fruits.each do |pos, amount|
    steps[pos] = amount
  end

  right_sum = 0
  right_cumulative = start_pos.upto(start_pos + k).map do |i|
    right_sum += (steps[i] || 0)
  end

  left_sum = 0
  # Need to max because ruby will wrap around with negative indexes
  left_cumulative = start_pos.downto([0, start_pos - k].max).map do |i|
    left_sum += (steps[i] || 0)
  end

  # puts right_cumulative.inspect
  # puts left_cumulative.inspect
  # puts steps[start_pos]

  start_fruit = (steps[start_pos] || 0)

  right_first = right_cumulative.each_with_index.map do |right_sum, rightmost|
    # right first, then turn left
    # We need to bound it within left_cumulative.length - 1, so that we're getting the maximum left sum if we exceed the bounds
    leftmost = [[0, k - rightmost * 2].max, left_cumulative.length - 1].min
    
    # left/right cumulative include the start_fruit, so we subtract to avoid double counting.
    # because of the subtraction, if there is no left cumulative sum, then we add start_fruit
    [right_sum + (left_cumulative[leftmost] || start_fruit) - start_fruit, [leftmost, rightmost, 'right-first']]
  end
  
  left_first = left_cumulative.each_with_index.map do |left_sum, leftmost|
    # left first, then turn right
    rightmost = [[0, k - leftmost * 2].max, right_cumulative.length - 1].min
    [left_sum + (right_cumulative[rightmost] || start_fruit) - start_fruit, [leftmost, rightmost, 'left-first']]
  end

  (right_first + left_first).max[0]
end