max.rb

# 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