def max_time(input)
  result = []
  input.each_key do |id|
    sum = 0
    result.push(total_duration(input, id, sum))
  end
  result.max
end

def total_duration(input, start_id, sum)
  current_task = input[start_id]
  sum += current_task[:duration]
  return sum if current_task[:dependency] == -1
  dep_id = current_task[:dependency]
  total_duration(input, dep_id, sum)
end

input1 = { 1 => { duration: 3, dependency: -1 },
           2 => { duration: 5, dependency: -1 },
           3 => { duration: 4, dependency: 1 } }
input2 = { 1 => { duration: 3, dependency: 2 },
           2 => { duration: 5, dependency: -1 },
           3 => { duration: 4, dependency: 1 } }
input3 = { 1 => { duration: 3, dependency: 2 },
           2 => { duration: 5, dependency: -1 },
           3 => { duration: 4, dependency: 1 },
           4 => { duration: 6, dependency: 3 } }
p max_time(input1)
p max_time(input2)
p max_time(input3)