Create a gist now

Instantly share code, notes, and snippets.

@poyo-poyo /LIS.rb
Last active Apr 29, 2017

What would you like to do?
LongestIncreasingSubsequence(strictly increasing)
class SegmentTree
def initialize(n)
@root, @nil=0, 0
@sz=2**(Math.log(n)/Math.log(2)).ceil
@seg=Array.new(2*@sz-1){@nil}
end
attr_accessor :seg
def max(a, b, i=@root, l=0, r=@sz)
if b<=l or r<=a
@nil
elsif a<=l and r<=b
@seg[i]
else
m=(r+l)/2
vl=max(a, b, 2*i+1, l, m)
vr=max(a, b, 2*i+2, m, r)
[vl, vr].max
end
end
def update(i, data)
i+=@sz-1
@seg[i]=data
while i.nonzero?
i=(i-1)/2
@seg[i]=[@seg[2*i+1], @seg[2*i+2]].max
end
end
def answer
@seg[@root]
end
end
Poyo=Struct.new(:val, :id)
n=gets.to_i
a=[]
n.times do |i|
v=gets.to_i
a<< Poyo.new(v, i)
end
b=a.sort do |el, er|
el.val!=er.val ? el.val<=>er.val : er.id<=>el.id
end
st=SegmentTree.new(n)
b.each do |e|
i=e.id
st.update(i, st.max(0, i)+1)
end
puts st.answer
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment