最長増加部分列（LIS）

螺旋本読んでもLISがわかんなかった。
以下のページがとてもわかり易かった。
最長増加部分列・最長共通部分列 [いかたこのたこつぼ]

誤解してたこと
・Lは昇順に並んでいるから、これが最長増加部分列になると思ってた。
・そうじゃなく、異なる長さの増加部分列の "それぞれ" の末尾要素を集めただけ。
・昇順に並んではいるが、Lの要素たちは独立。

アルゴリズムの解説（だいぶ簡略化、厳密じゃないです）
・Lは異なる長さの増加部分列を作ったときに末尾要素が取る値の配列
・Lの末尾より大きい要素が来たら、Lに要素を追加。 #1
・Lの末尾より大きくなかったら、Lの適切な位置を上書き。 #2
（そのときに作れる増加部分列を更新し、末尾のみ記憶してるイメージ）

def lis2(arr)
  dp = [] #Lの代わりにdpを使ってます
  dp[0] = arr[0]
  arr[1..-1].each do |a|
    if a > dp[-1]
      #1 増加部分列に追加
      dp.push(a)
    else
      #2 適切な位置を上書き
      b = dp.find_index { |n| n > a }
      dp[b] = a
    end
  end
  dp.length
end

# 考え方は簡単だけど、O(n^2)かかるバージョン
def lis(arr)
  dp = Array.new(arr.length, 1)
  (0...arr.length).each do |i|
    (0...i).each do |j|
      dp[i] = [dp[j] + 1, dp[i]].max if arr[j] < arr[i]
    end
  end
  dp.length
end