最長増加部分列問題

lis.rb

## 最長増加部分列問題
## http://rubyfiddle.com/riddles/2031d

a = [4,2,3,1,5]
n = a.size

dp = Array.new(n+1,nil)
res =0

n.times{|i|
  dp[i]= 1
  j=0
  while j < i
    if a[j] < a[i]
      dp[i] = [dp[i],dp[j]+1].max
    end
    j += 1
  end
  res = [res,dp[i]].max
  }
puts res