Finding subarray with maximum sum/number of elements

Question

Input: An array of n positive and negative numbers and a number k.

Output: Subarray of at least k consecutive elements with maximum sum of elements divided by number of elements in the subarray.

O(n^2) algorithm is easy. Does anyone have a better algorithm for this?

This looks more like a highest average subarray problem. Very similar. — Wug
– Wug, Commented Oct 26, 2012 at 20:07
Does the subarray have to be consecutive or are you looking for a subset? — Bitwise
– Bitwise, Commented Oct 26, 2012 at 20:09
This question has a trivial answer: just find the maximal element of the array. A one-element sub-array, containing this element is the maximum sum/size sub-array. — Evgeny Kluev
– Evgeny Kluev, Commented Oct 26, 2012 at 20:21
@EvgenyKluev Not true. Are you forgetting "negative" values? — im so confused
– im so confused, Commented Oct 26, 2012 at 20:30
@Wug do you have a link for "highest average subarray" problem? — Mohammad Moghimi
– Mohammad Moghimi, Commented Oct 26, 2012 at 20:32

IVlad · Accepted Answer · 2012-10-26 21:14:54Z

3

You can use binary search.

For a searched value x, consider the array b[i] = a[i] - x. Now find the maximum sum subarray of length at least k.

This works because the average of a subarray of length k is (a[p] + ... + a[p + k - 1]) / k. So we have:

(a[p] + ... + a[p + k - 1]) / k >= avg
a[p] + ... + a[p + k - 1] >= avg * k
(a[p] - avg) + ... + (a[p + k - 1] - avg) >= 0

So, if you binary search for the average, by substracting it from each element, if you can find a positive-sum subarray (find the maximum one and check if it's positive) of length at least k, then avg is a valid answer: continue to search in [avg, max_avg] to see if you can find a better one. If not, reduce search to [0, avg].

answered Oct 26, 2012 at 21:14

IVlad

43.6k13 gold badges115 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mohammad Moghimi Over a year ago

Makes sense. The runtime order becomes O(N)*log(range of numbers). It's still not clear for me when to stop the binary search.

IVlad Over a year ago

@MohammadMoghimi - you can stop it when the interval you're searching in becomes small enough for your purposes. Try stopping it when it becomes smaller than 10^-3 for example. If it's not good enough, decrease the exponent.

Collectives™ on Stack Overflow

Finding subarray with maximum sum/number of elements

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related