Author |
Topic: Longest Contiguous Subarray with average >= k (Read 4468 times) |
|
daunting
Newbie
Posts: 2
|
 |
Longest Contiguous Subarray with average >= k
« on: Nov 29th, 2011, 8:54am » |
 Quote  Modify
|
Consider an array of N integers. Find the longest contiguous subarray so that the average of its elements is greater than a given number k.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Longest Contiguous Subarray with average >=
« Reply #1 on: Nov 29th, 2011, 1:02pm » |
Quote Modify
|
One approach would be to create an array of running totals first; then search in that array for the pair of positions furthest apart where the difference in sums is greater than equal to the difference in position times the minimum average.
O(N2) overall.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
daunting
Newbie
Posts: 2
|
|
Re: Longest Contiguous Subarray with average >=
« Reply #2 on: Nov 30th, 2011, 6:26am » |
Quote Modify
|
Is it possible to improve it to something close to O(nlogn) or even linear maybe using DP?
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Longest Contiguous Subarray with average >=
« Reply #3 on: Dec 2nd, 2011, 6:14pm » |
Quote Modify
|
A greedy approach might just work.
Compute the average of the whole array. If the average is greater than k, return the whole array. If not, you have the choice of removing either the leftmost element or the rightmost. Choose the one which after its removal gives higher average. So on and so forth.
I haven't been able to prove correctness. Most likely there could be a easy counterexample that I am not seeing yet.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest Contiguous Subarray with average >=
« Reply #4 on: Dec 3rd, 2011, 11:15am » |
Quote Modify
|
As counter-example try 2 2 2 0 0 4 with k=2, the longest subarray with average >=2 is 2 2 2, but your algorithm would give 0 4
|
| « Last Edit: Dec 3rd, 2011, 11:41am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Longest Contiguous Subarray with average >=
« Reply #5 on: Dec 5th, 2011, 4:43am » |
Quote Modify
|
"find the longest subarray such that the average is >k"
subtract k from each element and it becomes
"find the longest subarray such that the average is >0"
which is equivalent to
"find the longest subarray such that the sum is >0"
And that can be done in O(n):
Set i=0, j=the last element such that sum from i to j is >0.
then repeat:
- check whether the sum is positive and (j-i) is larger than any value seen before. If yes, save (i,j).
- if the sum is >0, increase i else increase j
- stop when j reaches the end of the array.
the best subarray is given by the last saved (i,j)
note: the sum from i to j can be updated as you increase i and j.
[edit]
PS: oops, I realized it doesn't always work, but I think it is a good start.
|
| « Last Edit: Dec 5th, 2011, 4:56am by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Longest Contiguous Subarray with average >=
« Reply #6 on: Dec 6th, 2011, 2:48pm » |
Quote Modify
|
When you search for the last j that has a sum[0..j] >0, you must save all intermediate j's and sums where the sum is larger than any sum you have seen before (i.e. for a larger j).
Later, instead of just increasing j, you should only consider the j's and corresponding sums among those you saved.
And that means you need to compute sum[i..j] as sum[0..j] - sum[0..i-1].
|
|
IP Logged |
|
|
|
fizyka
Junior Member
Physics&Informa tics <3
Gender:
Posts: 54
|
|
Re: Longest Contiguous Subarray with average >=
« Reply #7 on: Dec 6th, 2011, 4:11pm » |
Quote Modify
|
this is pretty difficult riddle, I think little simulation in C programming language will be highly recommended.
But how to build algorithm like this?
|
|
IP Logged |
fizyka , karta wzorów fizyka , książki z fizyki
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Longest Contiguous Subarray with average >=
« Reply #8 on: Dec 22nd, 2011, 9:33am » |
Quote Modify
|
on Dec 6th, 2011, 2:48pm, Grimbal wrote:When you search for the last j that has a sum[0..j] >0, you must save all intermediate j's and sums where the sum is larger than any sum you have seen before (i.e. for a larger j).
Later, instead of just increasing j, you should only consider the j's and corresponding sums among those you saved.
And that means you need to compute sum[i..j] as sum[0..j] - sum[0..i-1]. |
|
Could you consolidate and explain your solution in detail. Would it work if after subtracting the k from each element, we have an array like this
[-2,2,0,2,-2,0,-1]
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Dufus
Newbie
Posts: 43
|
|
Re: Longest Contiguous Subarray with average >=
« Reply #9 on: Dec 25th, 2011, 2:56am » |
Quote Modify
|
Can someone please explain why this problem is NOT similar to classic maximum sum subvector problem?
I think if we define max subvector such that it is satisfies the average threshold and is the longest so far, we can solve this problem in O(N) time and O(1) space.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print