This one is O(n) time complexity, but there's still a weird bug coming up in the test cases...

Codility Flags Challenge

def create_peaks(a)
  peaks = [false]
  (1..a.size - 2).each do |i|
    if a[i] > a[i - 1] && a[i] > a[i + 1]
      peaks << true
    else
      peaks << false
    end
  end
  peaks
end

def next_peak(a)
  n = a.size
  peaks = create_peaks(a)
  next_map = Array.new(n).fill(0)
  next_map[n-1] = -1
  (a.size - 2).downto(-1).each do |i|
    if peaks[i]
      next_map[i] = i 
    else 
      next_map[i] = next_map[i+1]
    end
  end
  next_map
end

def solution(a)
  n = a.size 
  next_map = next_peak(a)
  num_flags = 1 
  max_flags = 0 
  while (num_flags-1) * num_flags <= n 
    pos = 0 
    num_placed = 0
    while pos < n && num_placed < num_flags 
      pos = next_map[pos]
      break if pos == -1
      num_placed += 1 
      pos += num_flags
    end 
    max_flags = [max_flags, num_placed].max
    num_flags += 1
  end
  max_flags
end