zakisan's blog

https://github.com/kenzan100

独学道場で、アルゴリズムの勉強を再開しています。

僕らが主催するプログラミング独学道場で、帰国後遠ざかっていた アルゴリズムの勉強を再開。 Manberという人が書いた「Introduction to Algorithms」の第1章の末尾、エクササイズの1.3をやった。

独学道場とは www.dokugaku.io

エクササイズ 1.3 は、訳すとこんな感じ。

「9, 44, 32, 12, 7, 42」のような順番で並ぶ数字のリストを考えてください。 このリストから、できるだけ少ない回数 数字を取り除いて、数字が大きくなる順で並ぶようなリストにしてください。

自分が唸って書いたRubyスクリプトは下記。もっと良いやり方あるよ! って方は、ぜひぜひ!コメントください。

require 'pp'
def make_ol(list)
  possible_arr = []
  list.each do |n|
    possible_arr.each do |arr|
      i = (arr.length - 1)
      while i >= 0
        if arr[i] < n
          arr.delete_if{ |m| m > n }
          arr << n
          break
        end
        i -= 1
      end
    end
    possible_arr << [n]
    pp possible_arr
  end
  possible_arr.max{ |a,b| a.length <=> b.length }
end

pp make_ol([9, 44, 32, 12, 7, 42])

Githubでも公開しているので、そちらの方がコメント送りやすければぜひGithub上でフィードバックください。

github.com