Maximum contiguous subarray average

Question

Take an array of integers and an integer K. For all contiguous subarrays of length at least K, return the maximum average value (sum of all elements in the subarray divided by length of subarray, rounded down).

You may write a full program or a function. Input is the array and K, in any reasonable form and order. The length of the array will always be at least K. The array may contain negative integers, and negative values round down (2.9 to 2, -2.1 to -3).

Sample test (length of array, K, then array):

5 2
7 1 6 2 8

Output:

5

The optimal range here is taking [2, 8]. (2 + 8) / 2 = 5. An answer of 8 is not possible, because the subarray [8] has length 1, and the minimum length is 2.

[6, 2, 8] is another optimal range, with value (6 + 2 + 8) / 3 = 5.333, rounded down to 5.

This is code-golf, so shortest code wins! (In bytes.)

Test cases for validation:

K	Array	Output
3	[7, 1, 6, 2, 8]	5
2	[7, 1, 7]	5
1	[1, 5, 7, 2, 9, 10]	10
3	[-2, -6, -8, -1, -17]	-5
5	[1, 2, 3, 4, 5]	3

• tata: May I assume the array contains at least K elements?
• Kevin Cruijssen: @tata I would assume the output is 5, since it asks for lengths of at least \$K\$. So the list is [7,1,7] with average 5.0 (sum 15 and length 3), 'rounded down' to 5.
• Kevin Cruijssen: @Redz "The optimal range here is taking [2, 8]. (2 + 8) / 2 = 5." You may want to add that [6,2,8] is an alternative optimal range with the same output: (6+2+8)/2=5.333..., rounded down to 5. (Both are valid, and 5 is the intended output.)
• Arnauld: Since it's not specified otherwise, I assume that the array may contain negative integers? Can you confirm that 2.9 should be rounded down to 2 and -2.1 to -3? More test cases would be welcome.
• Graham: Should the answer to your negative integer example be -5?

Answer 1

Google Sheets, 123 bytes

=SORT(MAX(MAP(A2:A,LAMBDA(a,MAP(SEQUENCE(1,COUNT(A2:A)-A1+1,A1),LAMBDA(i,IFERROR(INT(1/AVERAGE(N(OFFSET(a,,,i)))^-1))))))))

Expects K in A1 and the array from A2 onwards.

• doubleunary: I think you can cut 16 bytes with sequence(1,A1-A2+1,A2) and average(n(offset(a,,,i))).
• z..: thanks. I changed it a bit because the formulas weren't working with negative avgs and I thought the length of the array was part of the input.

Answer 2

05AB1E, 10 bytes

ŒʒgI@}ÅAàï

Inputs in the order \$list,K\$.

Try it online or verify both test cases.

Explanation:

Π# Get all sublists of the first (implicit) input-list
 ʒ # Filter it by:
 g # Get the length of the current sublist
 I@ # Check that it's >= the second input-integer
 }ÅA # After the filter: get the average of each remaining sublist
 à # Pop and keep the maximum
 ï # Floor it to an integer
 # (which is output implicitly as result)

Answer 3

Vyxal 3 -l, 11 (literate) bytes

sublists filter< 
 length second-input >=
} 
each: arithmetic-mean max-of 
floor

Vyxal It Online!

Could be a lot shorter if it wasn't at least K :p

Answer 4

Haskell, (削除) 98 (削除ここまで) (削除) 96 (削除ここまで) 77 bytes

k!a=maximum[(`div`x).sum.take x.drop y$a|x<-[k..length a],y<-[0..length a-x]]

Try it Online!

This is my first time golfing, so there might be more to save.

Edit: Saved more by using the list monad

• Themoonisacheese: Welcome to codegolf and nice first answer! you might want to checkout our tips for golfing in haskell thread :)

Answer 5

Jelly, 7 bytes

ẆṫƇÆmṀḞ

A dyadic Link that accepts the list of \$n\$ integers on the left and the minimal sublist length, \$k\$, on the right and yields the maximal floored mean of the sublists of at least length \$k\$.

Try it online!

How?

ẆṫƇÆmṀḞ - Link: list of integers, L; positive integer, K
Ẇ - all non-empty, contiguous sublists of L
 Ƈ - keep those for which:
 ṫ - tail from 1-index K (an empty list is falsey)
 Æm - mean (vectorises)
 Ṁ - maximum
 Ḟ - floor (towards -inf)

Answer 6

Ruby, 62 bytes

->l,k{(k..l.size).map{|n|l.each_cons(n).map(&:sum).max/n}.max}

Attempt This Online!

Thanks Value Ink for the fixes and for -2 bytes on the final version.

• Value Ink: The presence of the 0 causes test cases with only negative numbers to give the wrong answer. Thankfully, switching from recursion to a map call fixes the problem and saves 2 bytes: ->l,k{(k..l.size).map{|n|l.each_cons(n).map(&:sum).max/n}.max}

Answer 7

Python 2, 68 bytes

f=lambda a,k:max([sum(a)/len(a)]+(a[k:]and[f(a[1:],k),f(a[:-1],k)]))

Try it online!

Answer 8

Desmos, 85 bytes

l=L.count
a=floor(L.total/l)
f(L,k)=\{l>k:[f(L[2...],k),f(L[1...l-1],k),a],[a]\}.\max

Port of tata's Python 2 answer so make sure to upvote that as well.

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 9

APL(Dyalog Unicode), ^{(削除) (削除ここまで)}24 bytes ^SBCS

{⌈/∊(⍺↓0,⍳≢⍵)(⌊+/÷⊣) ̈⊂⍵}

Try it on APLgolf!

K is the left argument and an array is the right.

Explanation

 ⍵ the right argument (an array)
 ⊂ Enclose (to treat the entire array as one scalar)
 ̈ Each
 ( ) tacit function: X (e f g h) Y ←→ e (X f Y) g (X h Y)
 ⊣ Left argument
 ÷ Divide
 / (n-wise) Reduction
 + 
 +/ n-wise sum
 ⌊ Round down
 (⌊+/÷⊣) rounded down rolling average
 ( ) 
 ⍵ 
 ≢ Tally (length)
 ⍳ Index Generator (numbers from 1 to a right argument)
 , Concatenate
 0 
 ↓ Drop
 ⍺ the left argument (K)
 (⍺↓0,⍳≢⍵) numbers from K to the length of array
 (⍺↓0,⍳≢⍵)(⌊+/÷⊣) ̈⊂⍵ averages of all contiguous subarrays of length at least K, combined by the length
 ∊ Enlist (list all values in one vector)
 / Reduce
 ⌈ Maximum
{⌈/∊(⍺↓0,⍳≢⍵)(⌊+/÷⊣) ̈⊂⍵} solution

Answer 10

APL+WIN, 33 bytes

Prompts for k followed by vector of integers.

⌈/⌊(∊⌈/ ̈k+/ ̈⊂n)÷k←k+0,⍳(⍴n←⎕)-k←⎕

Try it online! Thanks to Dyalog Classic

Explanation

k←⎕ Prompt for k and assign to the variable
n←⎕ Prompt for n and assign to variable
⍴n Length of n
k←k+0,⍳ k becomes a vector of lengths k to ⍴n
k+/ ̈⊂n Sum successive elements of n by lengths k
∊⌈/ ̈ Find the maximum of each sum
(...)÷k Divide each sum by its length
⌈/⌊ Round down the resulting averages and find the maximum

• NooneAtAll3: how does it work?
• Graham: @NooneAtAll3 I have added an explanation to the answer.

Answer 11

Charcoal, 25 bytes

I⌈E...·θLη÷⌈E...·ιLηΣ✂η−λιλ1ι

Try it online! Link is to verbose version of code. Explanation:

 E Map over
 ...· Inclusive range from
 θ Input `K` to
 η Input array
 L Length
 E Map over
 ...· Inclusive range from
 ι Current value to
 η Input array
 L Length
 η Input array
 ✂ 1 Sliced from
 λ Inner value
 − Subtract
 ι Outer value
 λ To inner value
 Σ Take the sum
 ⌈ Take the maximum
 ÷ Integer divided by
 ι Current value
 ⌈ Take the maximum
I Cast to string
 Implicitly print

Answer 12

Maple, 77 bytes

(A,K)->max(seq(seq(floor(add(A[i..i+k-1])/k),i=1..n-k+1),k=K..(n:=nops(A))));

Input is list A and positive integer K.

Answer 13

Uiua 0.17.0-dev.1, 24 bytes ^SBCS

⌊/↥/◇⊂⍚⌟⧈(÷⊃⧻/+)⊂⊸⍜-⇡⊙⊸⧻

Try on Uiua Pad!

Explanation

 ⊙⊸⧻ # place length of arr beneath k
 ⊂⊸⍜-⇡ # inclusive range from k to len(arr)
 ⍚⌟ # map over range, fixing input arr and boxing output
 ⧈(÷⊃⧻/+) # windows by mean
 /◇⊂ # concat boxed arrays
 /↥ # maximum
⌊ # floor

Answer 14

Go, (削除) 213 (削除ここまで) (削除) 188 (削除ここまで) 178 bytes

Saved (25+10=35) bytes thanks to @ceilingcat

Golfed version. Attempt This Online!

import"slices"
func f(l[]int,k int)int{if len(l)<k{return 0}
s:=[]int{}
for i:=range-^len(l)-k{t:=0
for j:=range k{t+=l[i+j]}
s=append(s,t)}
return max(slices.Max(s)/k,f(l,k+1))}

Ungolfed version. Attempt This Online!

package main
import "fmt"
// This function calculates the maximum average of consecutive elements in an array using integer division
func f(list []int, windowSize int) int {
	// Base case: if the window size is larger than the list, return 0
	if len(list) < windowSize {
		return 0
	}
	// Calculate the sum of each consecutive window of elements
	var sumsOfWindows []int
	for i := 0; i <= len(list)-windowSize; i++ {
		sum := 0
		for j := 0; j < windowSize; j++ {
			sum += list[i+j]
		}
		sumsOfWindows = append(sumsOfWindows, sum)
	}
	// Find the maximum sum and calculate the average (integer division)
	maxSum := max(sumsOfWindows)
	currentMaxAverage := maxSum / windowSize
	// Recursively find the max average with a larger window size
	nextWindowMaxAverage := f(list, windowSize+1)
	// Return the larger of the two averages
	if currentMaxAverage > nextWindowMaxAverage {
		return currentMaxAverage
	}
	return nextWindowMaxAverage
}
// Helper function to find maximum in a slice of integers
func max(slice []int) int {
	if len(slice) == 0 {
		return 0
	}
	maxVal := slice[0]
	for _, v := range slice {
		if v > maxVal {
			maxVal = v
		}
	}
	return maxVal
}
func main() {
	fmt.Println(f([]int{7, 1, 6, 2, 8}, 2)) // Should output 7
	fmt.Println(f([]int{7, 1, 7}, 2)) // Should output 4
}

Answer 15

Rust, 102 bytes

|a,k|(k..=a.len()).flat_map(|l|a.windows(l).map(move|x|x.iter().sum::<i64>().div_floor(l
as _))).max()

Playground

Answer 16

JavaScript (ES6), 85 bytes

Expects (K)(array).

k=>g=([v,...a],n=0,s=0,i)=>q=!i/v?g(a,n+1,s+v)<g(a,n,s,n,v=q)?q:v:n<k?g:s/n-(s%n<0)|0

Try it online!

Commented

k => // outer function taking k
g = ( // g = inner recursive function taking:
 [ v, // v = current value from the input array
 ...a // a[] = remaining values
 ], //
 n = 0, // n = number of values in the subarray
 s = 0, // s = sum of all values in the subarray
 i // i = flag set when the subarray is closed
) => //
q = // save the result of this call in q
!i / v ? // if i is not set and v is defined:
 g( // 1st recursive call where:
 a, n + 1, s + v // v is included in the subarray
 ) //
 < // (compare)
 g( // 2nd recursive call where:
 a, n, s, // v is not included in the subarray
 n, // i is set if n is not 0
 v = q // the result of the 1st call is saved in v
 ) ? // if v (1st call) is less than q (2nd call):
 q // return q
 : // else:
 v // return v
: // else:
 n < k ? // if n is less than the target k:
 g // invalidate this result
 : // else:
 s / n // return s / n
 - (s % n < 0) // -1 if this is a negative non-integer
 | 0 // rounded toward 0 (*)

_{(*) This is a twisted and 2-byte shorter way of just doing Math.floor(s/n).}