計算アルゴリズム

系列長が同じものでは最大値が最小のもののみを持てばいい点を押し進めると、
RBTreeの必要はまったくなくなっていることに気付きました。

class Sequence
　　def initialize(prev, max)
　　　　@prev = prev
　　　　@max = max
　　end
　　attr_reader :prev, :max

　　def result()
　　　　# 省略
　　end
end

def find_longest(ary)
　　sequences = Array.new(ary.length+1)
　　maxlen = 0
　　ary.each { |x|
　　　　j = maxlen
　　　　j -= 1 while j > 0 and sequences[j] and sequences[j].max >= x
　　　　len = j+1
　　　　maxlen = len if maxlen < len
　　　　s = sequences[len]
　　　　next if s and s.max < x
　　　　sequences[len] = Sequence.new(sequences[j], x)
　　}
　　sequences[maxlen].result
end