Find the maximum deviation

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.

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.

JavaScript (ES6), 73 bytes

with(Math)(v,d)=>max(...v.map((a,i)=>max(...a=v.slice(i,i+d))-min(...a)))
• +1 for TIL that you can use with on an entire lambda function Oct 21 '16 at 15:18
• Actually, Uncaught SyntaxError: Unexpected token with. Can you post a working snippet? Oct 21 '16 at 15:21
• @BassdropCumberwubwubwub If you want to name the lambda you need to put the assignment after the with(Math), or use f=eval("with(Math)(v,d)=>max(...a)))").
– Neil
Oct 21 '16 at 15:43

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)
• I think you can just use v and; the range isn't going up if you remove elements.
– Neil
Oct 21 '16 at 14:48

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[abs1-&]})\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) • I see a regex, and then I get lost. 0.0 What's going on here? Oct 21 '16 at 19:09 • @VTCAKAVSMoACE Basically I match 1 to width consecutive lines.$& will contain the whole match which will evaluate as the first number in arithmetic context. $1 will contain the last number. I then forcefully fail the regex with \A. So it will try all starting positions and lengths up to width. I use absolute value of the difference as an array index and see how big the array grows. Perl has no builtin max so I have to improvise Oct 21 '16 at 19:13 • That's extremely clever. Any way you can put the -0pi3 -e into -0pi3e? Just an assumption about a possible reduction, I don't use perl (thus my question). Oct 21 '16 at 19:16 • @VTCAKAVSMoACE No unfortunately. -i eats everything after it as its value, including any e Oct 21 '16 at 19:18 • And I'm assuming that -e has to go just before the code? Bummer. Oct 21 '16 at 19:21 R, 6362 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)) • Nice, I knew there was a function for generating the subsequences but couldn't find it. Also behind a proxy at work so can't use any external packages. Oct 21 '16 at 15:25 • Some googling informs me that there's also gtools::rolling, but that's one more byte and I'm not familiar with it. I'm always in two minds about using non-base packages: on the one hand, it feels like cheating when there's a simple solution; on the other hand, the packages (and the community) are one of R's strengths as a language, I think. Oct 21 '16 at 15:30 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)])))) • You can replace 1:(length(s)-d+1) with d:sum(1|s)-d+1. Oct 21 '16 at 14:44 • @rturnbull Nice catch! Oct 21 '16 at 14:47 Husk, 13 7 bytes ▲m§-▼▲X Try it online! -6 bytes from Jo King. Explanation ▲m§-▼▲X Slices of length n m map to §- difference between ▼▲ min and max ▲ take the maximum of that • @JoKing Imagine reading documentation Oct 6 '20 at 10:01 PowerShell v2+, 68 bytes param($v,$d)($v|%{($x=$v[$i..($i+++$d-1)]|sort)[-1]-$x}|sort)[-1]

(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

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)>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 ;
}

_#[]=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. 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 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;} 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 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 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();} 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 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 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.