プログラミングコンテストチャレンジブック演習「最長増加部分列問題」

今回のお題はこちら

A = [4,2,3,1,5] #input

$dp = Array.new(A.length, 1)
for i in 0..(A.length - 1)
  for j in 0..i
    $dp[i] = [$dp[i], $dp[j] + 1].max if A[i] > A[j]
  end
end

puts $dp.max