アルゴリズムとデータ構造1の回答

回答例1

arrs = [5, 3, 1, 3, 4, 3, 7, 8, 15]
cal_i = 0
arr_size = arrs.size
max_diff_val = arrs[1] - arrs[0]
arrs.each_with_index do |val, index|
  max_diff_val2 = 0
  idx = index + 1
  arrs[idx...arr_size].each do |val2|
    cal_i += 1
    if val2 > max_diff_val2
       max_diff_val2 = val2
    end
  end
  max_diff_val = max_diff_val2 - val if index == 0
  max_diff_val = max_diff_val2 - val if (max_diff_val2 - val) > max_diff_val
end

puts max_diff_val
puts cal_i

14と36が表示される。
計算量はO(n^2)

回答例2

arrs = [5, 3, 1, 3, 4, 3, 7, 8, 15] #14
cal_i = 0
arr_size = arrs.size
max_diff_val = arrs[1] - arrs[0]
min_val = arrs.first
arrs[1...arr_size].each do |val|
  max_diff_val = val - min_val if (val - min_val) > max_diff_val
  min_val = val if val < min_val
  cal_i += 1
end

puts max_diff_val
puts cal_i

14と8が表示される。
2番目の方がいい。
計算量はO(n)

計算量の比較