Find the maximum deviation

Question

This problem is "inspired" from a question that was originally asked on Quora (not for code golfing). I just want to make it a challenge for you guys (and my first problem submission here).

Given an array of integer elements v and an integer d (we assume that d is lower or equal to the array's length), consider all the sequences of d consecutive elements in the array. For each sequence, compute the difference between the maximum and minimum value of the elements in that sequence and name it the deviation.

Your task is to write a program or function that computes the maximum value among all deviations of all the sequences considered above, and return or output that value.

Worked-through Example:

v: (6,9,4,7,4,1)
d: 3

The sequences of length 3 are:
6,9,4 with deviation 5
9,4,7 with deviation 5
4,7,4 with deviation 3
7,4,1 with deviation 6

Thus the maximal deviation is 6, so the output is 6.

This is code golf, so the shortest answer in bytes wins.

Answer 1

Dyalog APL, 7 bytes

⌈/⌈/-⌊/

Test it on TryAPL.

How it works

⌈/⌈/-⌊/  Dyadic chain. Left argument: d. Right argument: v

     ⌊/  Reduce v by d-wise minimum, yielding the minima of all slices of length d.
  ⌈/     Reduce v by d-wise maximum, yielding the maxima of all slices of length d.
    -    Subtract, yielding the ranges of all slices of length d.
⌈/       Take the maximum.

Answer 2

JavaScript (ES6), 73 bytes

with(Math)(v,d)=>max(...v.map((a,i)=>max(...a=v.slice(i,i+d))-min(...a)))

Answer 3

Python, 60 bytes

Saving 5 bytes thanks to Neil

f=lambda v,d:v and max(max(v[:d])-min(v[:d]),f(v[1:],d))or 0

My first recursive lambda!

Usage:

print f([6,9,4,7,4,1], 3)

Answer 4

R, 63 62 56 bytes

Billywob has already provided a great R answer using only the base functions. However, I wanted to see if an alternative approach was possible, perhaps using some of R's extensive packages. There's a nice function rollapply in the zoo package designed to apply a function to a rolling window of an array, so that fits our purposes well. We use rollapply to find the max of each window, and we use it again to find the min of each window. Then we take the difference between the maxes and mins, which gives us the deviation for each window, and then return the max of those.

function(v,d)max((r=zoo::rollapply)(v,d,max)-r(v,d,min))

Answer 5

Perl, 48 bytes

Includes +5 for -0pi

Give the width after the -i option, give the elements as separate lines on STDIN:

perl -0pi3 -e '/(^.*\n){1,$^I}(?{\$F[abs$1-$&]})\A/m;$_=$#F'
6
9
4
7
4
1
^D

Just the code:

/(^.*\n){1,$^I}(?{\$F[abs$1-$&]})\A/m;$_=$#F

(use a literal \n for the claimed score)

Answer 6

R, 80 77 bytes bytes

Edit: Saved 3 bytes thanks to @rturnbull

function(s,d)max(sapply(d:sum(1|s)-d+1,function(i)diff(range(s[i:(i+d-1)]))))

Answer 7

05AB1E, 12 10 bytes

Uses CP-1252 encoding.

Œù€{øÀ`-ÄZ

Try it online!

Explanation

Π             # sublists of v
 ù             # of length d
  €{           # sort each
    ø          # zip
     À         # rotate left (last 2 lists will be largest and smallest)
      `        # flatten (lists with smallest and largest item will be on top)
       -       # subtract largest from smallest
        Ä      # take absolute value (as we will have negatives after the previous step)
         Z     # take the largest

Answer 8

PowerShell v2+, 68 bytes

param($v,$d)($v|%{($x=$v[$i..($i+++$d-1)]|sort)[-1]-$x[0]}|sort)[-1]

Iterative solution. Loops through $v, but really we're just using that as a counter rather than actually going through the values. Each iteration, we're slicing $v by $i..($i+++$d-1), where $i defaults to 0. We |sort those elements, and store the result into $x. Then we take the biggest [-1] and subtract the smallest [0]. We then |sort those results and take the biggest [-1] of that. That number is left on the pipeline and output is implicit.

Examples

PS C:\Tools\Scripts\golfing> .\find-the-maximum-deviation.ps1 @(6,9,4,7,4,1) 3
6

PS C:\Tools\Scripts\golfing> .\find-the-maximum-deviation.ps1 @(1,2,3,4,5,6) 3
2

PS C:\Tools\Scripts\golfing> .\find-the-maximum-deviation.ps1 @(7,2,3,4,5,6) 3
5

Answer 9

Mathematica, 41 37 bytes

Max[MovingMap[MinMax,#,#2-1].{-1,1}]&

Answer 10

Java 8, 140 128

Shaved a bunch off, in part thanks to VTCAKAVSMoACE.

int l(int[]a,int d){int x=0,i=0,f,j,k;for(;i<=a.length-d;i++)for(j=i;j<i+d;j++)for(k=i;k<i+d;)x=(f=a[j]-a[k++])>x?f:x;return x;}

Ungolfed

int l(int[]a,int d){
    int x=0,i=0,f,j,k;
    for(;i<=a.length-d;i++)
        for(j=i;j<i+d;j++)
            for(k=i;k<i+d;)
                x=(f=a[j]-a[k++])>x?f:x;
    return x;
}

Answer 11

Ruby, 45 bytes

->a,d{a.each_cons(d).map{|b|b.max-b.min}.max}

I feel like this could be a lot better.

Answer 12

MATL, 10 bytes

YCS5LY)dX>

Try it online!

Explanation

Consider inputs [6,9,4,7,4,1], 3 as an example.

       % Implicitly take the two inputs: v, d
       % STACK: [6,9,4,7,4,1], 3
YC     % Matrix of overlapping d-blocks of v
       % STACK: [6 9 4 7
                 9 4 7 4
                 4 7 4 1]
S      % Sort each column
       % STACK: [4 4 4 1
                 6 7 4 4
                 9 9 7 7]
5LY)   % Keep first and last rows
       % STACK: [4 4 4 1
                 9 9 7 7]
d      % Differences along each column
       % STACK: [5 5 3 6]
X>     % Maximum
       % STACK: 6
       % Implicitly display

Answer 13

MATLAB with Statistics and Image Processing Toolboxes, 33 bytes

@(v,d)max(range(im2col(v,[1 d])))

This defines an anonymous function. Example use:

>> f = @(v,d)max(range(im2col(v,[1 d])));
>> f([6,9,4,7,4,1], 3)
ans =
     6

You can also try it on Octave at Ideone (but Octave, unlike Matlab, requires explicitly loading the image package).

Explanation

im2col(v,[1 d]))   % Takes overlapping blocks of size d from v, and arranges them as
                   % columns of a matrix
range(...)         % Maximum minus minimum of each column. Gives a row vector
max(...)           % Maximum of the above row vector

Answer 14

PHP, 89 87 bytes

for($i=1;$r=array_slice($argv,++$i,$argv[1]);$d=max($r)-min($r))$o=$d>$o?$d:$o;echo+$o;

Not particularly clever or pretty but it works. Use like:

php -r "for($i=1;$r=array_slice($argv,++$i,$argv[1]);$d=max($r)-min($r))$o=$d>$o?$d:$o;echo+$o;" 3 6 9 4 7 1

for v=6,9,4,7,4,1, d=3

Edit: 2 bytes saved thanks to Jörg Hülsermann

Answer 15

Scala, 48 bytes

(_:Seq[Int])sliding(_:Int)map(s=>s.max-s.min)max

Ungolfed:

(a:Seq[Int],d:Int)=>a.sliding(d).map(s=>s.max-s.min).max

Explanation:

(_:Seq[Int])   //define a function with a seq of ints as an argument
sliding(_:Int) //get the sequences with the length of an int argument
map(s=>        //map each sequence
  s.max-s.min    //to its deviation
)max           //and take the maximum value

Answer 16

Actually, 13 bytes

╗╜@V`;m@M-`MM

Try it online!

-6 bytes from the observation in nimi's Haskell answer, that slices shorter than d don't affect the maximum deviation.

Explanation:

╗╜@V`;m@M-`MM
╗              store d in register 0
 ╜@            push d, swap so v is on top
   V           push all slices of v whose length is in [1, d]
    `;m@M-`M   map (for each slice):
     ;m@M-       get minimum and maximum, subtract min from max
           M  get maximum of list of deviations

Answer 17

Clojure, 73 67 bytes

Edit: Using #(...) instead of (fn[...]) and for instead of map.

#(apply max(for[p(partition %2 1 %)](-(apply max p)(apply min p))))

Answer 18

Pyth, 11 bytes

eSms.+Sd.:F

Explanation

eSms.+Sd.:FQ   Implicit input
          FQ   Unpack the input (v, d)
        .:     Get all subsequences of length d
  m   Sd       Sort each
   s.+         Take the sum of differences to get the deviation
eS             Get the maximum

Answer 19

Jelly, 8 bytes

ṡµṂ€ạṀ€Ṁ

Try it online!

Uses the same algorithm as Dyalog APL, but I figured this myself before looking at it.

Explanation:

ṡµṂ€ạṀ€Ṁ ḷ“Main link. Arguments: v d.”
ṡ        ḷ“Overlapping sublists of x of length y.”
 µ       ḷ“Start a new monadic chain.”
  Ṃ€ạṀ€  ḷ“Find the deviation of each of the elements of x.”
       Ṁ ḷ“Take the maximum of x.”

Note: x, y are left, right arguments respectively.

Answer 20

Perl 6, 44 bytes

{$^a.rotor($^b=>1-$^b).map({.max-.min}).max}

$^a and $^b are the two arguments to the function, called v and d respectively in the problem statement. The rotor method returns the sequence of subsequences of v of size d.

Answer 21

Python 3, 80 bytes

lambda v,d:max(map(lambda g:max(g)-min(g),[v[i:i+d]for i in range(-~len(v)-d)]))

Answer 22

CJam, 17 bytes

q~ew{$)\(\;-}%:e>

(Also q~ew:$z)\(\;.-:e>)

Try it online!

Explanation

q~                   e# Read the two inputs. Evaluate
  ew                 e# Overlapping blocks
    {       }%       e# For each block
     $               e# Sort
      )              e# Get last element (that is, maximum)
       \(            e# Swap, get first element (minimum)
         \;          e# Swap, delete rest of the block
           -         e# Subtract (maximum minus minimum)
              :e>    e# Maximum of array

Answer 23

Java 7,159 bytes

Java = expensive(i know it can be golfed much more)

int c(int[]a,int d){int[]b=new int[d];int i,j,s=0;for(i=-1;i<a.length-d;){for(j=++i;j<i+d;)b[i+d-1-j]=a[j++];Arrays.sort(b);s=(j=b[d-1]-b[0])>s?j:s;}return s;}

Ungolfed

static int c ( int []a , int d){
    int []b = new int[ d ];
    int i , j , s = 0 ;
    for ( i = -1 ; i < a.length - d ;) {
        for ( j = ++i ; j < i + d ;)
        b[ i + d - 1 - j ] = a[ j++ ] ;
        Arrays.sort( b ) ;
        s = ( j = b[ d - 1 ] - b[ 0 ] ) > s ? j : s ;
    }
    return s ;
    }

Answer 24

Haskell, 56 bytes

_#[]=0 
d#l|m<-take d l=max(maximum m-minimum m)$d#tail l

Usage example: 3 # [6,9,4,7,4,1] -> 6.

Considering ranges less than d doesn't change the overall maximum, so we can run take d down to the very end of the list (i.e. also include the ranges with the last d-1, d-2, ... 0 elements). The recursion stops with the empty list where we set the deviation to 0.

Answer 25

Java, 126 bytes

I got inspired by dpa97's answer and found this:

int f(int v[],int d){int m=0,i=0,j,t,l=v.length;for(;i<l;i++)for(j=i;j<l;j++)m=j-i<d&&(t=Math.abs(v[i]-v[j]))>m?t:m;return m;}

Expanded, golfed and example code

Answer 26

Racket 121 bytes

(let p((v v)(j 0))(let*((l(take v d))(k(-(apply max l)(apply min l)))
(j(if(> k j)k j)))(if(= d(length v))j(p(cdr v)j))))

Ungolfed:

(define (f d v)
  (let loop ((v v)
             (mxdev 0))                     ; start with max deviation as 0
    (let* ((l (take v d))                   ; take initial d elements in v
           (dev (- (apply max l)            ; find deviation
                    (apply min l)))
           (mxdev (if(> dev mxdev)          ; note max deviation
                   dev
                   mxdev)))
      (if (= d (length v)) mxdev            ; if all combinations tested, print max deviation
          (loop (rest v) mxdev))            ; else test again 
      )))                                   ; with first element of list removed

Testing:

(f 3 '(6 9 4 7 4 1))

Output:

6

Answer 27

q, 25 bytes

{max mmax[y;x]-mmin[y;x]}

mmax and mmin are sliding window maximum and minimum respectively

Example

q){max mmax[y;x]-mmin[y;x]}[6 9 4 7 4 1;3]
6

Answer 28

C#, 131 bytes

here is a verbose linq solution

int c(int[]a){var x=from j in Enumerable.Range(0,a.Length-2)let p=new[]{a[j],a[j+1],a[j+2]}select p.Max()-p.Min();return x.Max();}

Answer 29

C#, 163 bytes

Golfed:

int m(List<int> v,int d){var l=new List<List<int>>();for(int i=0;i<v.Count;i++){if(v.Count-i>=d)l.Add(v.GetRange(i,d));}return l.Select(o=>o.Max()-o.Min()).Max();}

Ungolfed:

public int m(List<int> v, int d)
{
  var l = new List<List<int>>();

  for (int i = 0; i < v.Count; i++)
  {
    if (v.Count - i >= d)
      l.Add(v.GetRange(i, d));
  }

  return l.Select(o => o.Max() - o.Min()).Max();
}

Test:

var maximumDeviation = new MaximumDeviation();
Console.WriteLine(maximumDeviation.f(new List<int> {6,9,4,7,4,1}, 3));

Output:

6