Skip to content

Instantly share code, notes, and snippets.

@shitpoet
Created February 17, 2016 07:37
Show Gist options
  • Save shitpoet/34a612d46f146ef683ce to your computer and use it in GitHub Desktop.
Save shitpoet/34a612d46f146ef683ce to your computer and use it in GitHub Desktop.
# support sliding window maximum in linear time
srand(123)
n = 9
k = 3
m = n-1
a = (0..m).to_a
for i in 0..m do
#a[i] = (rand()*10).floor()
a[i] = (9-i).floor()
end
a = [5, 3, 6, 7, 4, 6, 1, 2, 9]
puts a.to_s
def calc_q(a, i, k)
q = (i..(i+k-1)).to_a
max = 0
for j in 0..(k-1) do
jj = (k-1)-j
#puts 'a['+(i+jj).to_s+'] to q['+jj.to_s+']'
max = [max, a[i+jj]].max
q[jj] = max
end
q
end
def print_q(q)
puts 'q: '+(q.map{|el| el.to_s}).join(' ')
end
q = calc_q(a, 0, k)
print_q(q)
puts 'M: '+q[0].to_s
nw = 0
for i in 1..(n-k) do
puts ' '*(i*3) + a[i..(i+k-1)].to_s # window
if i % k == 0
q = calc_q(a, i, k)
puts ' '*(i*3) + 'q*: '+(q.map{|el| el.to_s}).join(' ')
qm = q[0]
nw = 0
m = qm
else
q.shift
qm = q[0]
puts ' '*(i*3) + 'q: '+(q.map{|el| el.to_s}).join(' ')
puts ' '*(i*3) + 'qm: '+qm.to_s
ai = a[i+k-1]
puts ' '*(i*3) + 'a[i+k-1]: '+ai.to_s
nw = [nw,ai].max
puts ' '*(i*3) + 'nw: '+nw.to_s
end
m = [qm,nw].max
puts ' '*(i*3) + 'M: '+m.to_s
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment