Finding maximum deviation

It was a part of my coding challenge and the last one, but I failed because it failed to yield a result in two seconds for some of sample inputs (out of six samples, three passed but three failed for not meeting the time constraint).

Basically, you are supposed to find the maximum deviation from given number of consecutive integers. There are two inputs; the first argument is an array of integers and the second argument is the number of consecutive integers. And you print the maximum deviation. For example, if you have [10, 1, 5, 2, 6, 3] and 3 as arguments, the output should be 9 since [10, 1, 5] would yield the maximum deviation of 9 (10-1).

Can this be refactored to be faster?

def find_deviation(integers, range)
  max = 0
  (0..integers.size-range).each do |n|
    array = integers.slice(n, range)
    diff = array.max - array.min
    max = diff if diff > max
  end
  puts max
end

Some notes:

-
find_deviation(v, d): Try to write more meaningful names for variables. Specially, I'd give a plurar name to v, since it's a collection.

-
max = 0, each, inline if: All of this denote you think in imperative terms. Some notes on functional programming with Ruby.

I'd write, with a functional approach:

def find_deviation(values, m)
  values.each_cons(m).map { |xs| xs.max - xs.min }.max
end

Now, this function has exactly the same time complexity than yours (though it may be faster or slower depending on how Ruby works). The complexity is: len(values) = n -> O(n*m). Note that you can use Enumerable#minmax to avoid one traversal, but it's still the same complexity.

To make it faster here's an idea, even though it's not trivial to implement: use a structure with O(log n) times for insertion/deletion/max/min (a binary search tree is ideal for this) to hold values of the sliding window, this way the overall complexity is O(nlog m). I guess some of the tests have big values of m so the trivial approach O(nm) is too slow.

[edit] Just for fun, I wrote a O(n log m) implementation in Haskell (I found no BST gem for Ruby):

deviation :: (Num a, Ord a) => [a] -> Int -> a 
deviation [] _ = 0
deviation xs m = maximum $ [Tree.maximum w - Tree.minimum w | w <- windows]
  where
    windows = scanl shift (Tree.fromList $ take m xs) (zip xs (drop m xs))
    shift window (old, new) = Tree.insert (Tree.delete window old) new

StackExchange Code Review Q#41781, answer score: 10