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:

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 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, Commented May 30 at 8:21
@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.) — Kevin Cruijssen, Commented May 30 at 8:27
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. — Arnauld, Commented May 30 at 10:57

z.. · Accepted Answer · 2025-05-31 04:58:19Z

7

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.

edited May 31 at 4:58

answered May 30 at 4:49

z..

2,0791 gold badge2 silver badges17 bronze badges

1

\$\begingroup\$ I think you can cut 16 bytes with sequence(1,A1-A2+1,A2) and average(n(offset(a,,,i))). \$\endgroup\$
– doubleunary
Commented May 30 at 17:09
\$\begingroup\$ 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. \$\endgroup\$
– z..
Commented May 31 at 5:01

Add a comment |

lyxal · Accepted Answer · 2025-05-30 08:48:26Z

5

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

answered May 30 at 8:48

lyxal

35.3k2 gold badges68 silver badges147 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2025-05-30 08:24:37Z

4

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)

edited May 30 at 8:24

answered May 30 at 8:18

Kevin Cruijssen

135k14 gold badges152 silver badges389 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2025-05-30 19:20:50Z

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)

G B · Accepted Answer · 2025-05-31 12:31:32Z

4

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.

edited May 31 at 12:31

answered May 30 at 5:54

G B

23.3k1 gold badge22 silver badges55 bronze badges

\$\begingroup\$ 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} \$\endgroup\$
– Value Ink
Commented May 30 at 21:42

Add a comment |

Aiden Chow · Accepted Answer · 2025-05-30 12:05:51Z

3

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

answered May 30 at 12:05

Aiden Chow

14.4k1 gold badge21 silver badges59 bronze badges

Add a comment |

Graham · Accepted Answer · 2025-05-31 15:52:47Z

3

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

edited May 31 at 15:52

answered May 30 at 9:38

Graham

7,5761 gold badge15 silver badges13 bronze badges

\$\begingroup\$ how does it work? \$\endgroup\$
– NooneAtAll3
Commented May 31 at 12:52
1

\$\begingroup\$ @NooneAtAll3 I have added an explanation to the answer. \$\endgroup\$
– Graham
Commented May 31 at 15:54

Add a comment |

Ibozz91 · Accepted Answer · 2025-06-02 11:23:39Z

3

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

edited Jun 2 at 11:23

answered Jun 1 at 22:07

Ibozz91

1114 bronze badges

\$\begingroup\$ Welcome to codegolf and nice first answer! you might want to checkout our tips for golfing in haskell thread :) \$\endgroup\$
– Themoonisacheese
Commented Jun 2 at 8:50

Add a comment |

tata · Accepted Answer · 2025-05-30 07:33:49Z

2

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!

answered May 30 at 7:33

tata

64912 bronze badges

Add a comment |

Neil · Accepted Answer · 2025-05-30 16:01:13Z

Charcoal, 25 bytes

Ｉ⌈Ｅ…·θＬη÷⌈Ｅ…·ιＬηΣ✂η⁻λιλ¹ι

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

  Ｅ                         Map over
   …·                       Inclusive range from
     θ                      Input `K` to
       η                    Input array
      Ｌ                     Length
          Ｅ                 Map over
           …·               Inclusive range from
             ι              Current value to
               η            Input array
              Ｌ             Length
                  η         Input array
                 ✂    ¹     Sliced from
                    λ       Inner value
                   ⁻        Subtract
                     ι      Outer value
                      λ     To inner value
                Σ           Take the sum
         ⌈                  Take the maximum
        ÷                   Integer divided by
                        ι   Current value
 ⌈                          Take the maximum
Ｉ                           Cast to string
                            Implicitly print

Mat_rdv · Accepted Answer · 2025-05-31 11:03:44Z

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

dharr · Accepted Answer · 2025-05-30 19:19:44Z

1

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.

answered May 30 at 19:19

dharr

8862 silver badges7 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2025-05-31 08:41:28Z

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

chunes · Accepted Answer · 2025-05-31 21:00:30Z

1

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

edited May 31 at 21:00

answered May 31 at 20:50

chunes

27.6k3 gold badges29 silver badges55 bronze badges

Add a comment |

score 1 · Accepted Answer · 2025-06-01 02:15:37Z

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
}

corvus_192 · Accepted Answer · 2025-06-08 18:34:28Z

0

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

edited Jun 8 at 18:34

answered Jun 8 at 18:27

corvus_192

5,88215 silver badges25 bronze badges

Add a comment |

Stack Exchange Network

Maximum contiguous subarray average

16 Answers 16

Google Sheets, 123 bytes

Vyxal 3 `-l`, 11 (literate) bytes

05AB1E, 10 bytes

Jelly, 7 bytes

How?

Ruby, 62 bytes

Desmos, 85 bytes

APL+WIN, 33 bytes

Haskell, 98 96 77 bytes

Python 2, 68 bytes

Charcoal, 25 bytes

APL(Dyalog Unicode), 24 bytes ^SBCS

Explanation

Maple, 77 bytes

JavaScript (ES6), 85 bytes

Commented

Uiua 0.17.0-dev.1, 24 bytes ^SBCS

Explanation

Go, 213 188 178 bytes

Rust, 102 bytes

Your Answer

Linked

Hot Network Questions

Maximum contiguous subarray average

16 Answers 16

Google Sheets, 123 bytes

Vyxal 3 -l, 11 (literate) bytes

05AB1E, 10 bytes

Jelly, 7 bytes

How?

Ruby, 62 bytes

Desmos, 85 bytes

APL+WIN, 33 bytes

Haskell, 98 96 77 bytes

Python 2, 68 bytes

Charcoal, 25 bytes

APL(Dyalog Unicode), 24 bytes SBCS

Explanation

Maple, 77 bytes

JavaScript (ES6), 85 bytes

Commented

Uiua 0.17.0-dev.1, 24 bytes SBCS

Explanation

Go, 213 188 178 bytes

Rust, 102 bytes

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Hot Network Questions

Vyxal 3 `-l`, 11 (literate) bytes

APL(Dyalog Unicode), 24 bytes ^SBCS

Uiua 0.17.0-dev.1, 24 bytes ^SBCS