wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Longest Contiguous Subarray with average >= k
        
(Message started by: daunting on Nov 29^th, 2011, 8:54am)

Title: Longest Contiguous Subarray with average >= k
Post by daunting on Nov 29^th, 2011, 8:54am

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.

Title: Re: Longest Contiguous Subarray with average >=
Post by towr on Nov 29^th, 2011, 1:02pm

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(N²) overall.

Title: Re: Longest Contiguous Subarray with average >=
Post by daunting on Nov 30^th, 2011, 6:26am

Is it possible to improve it to something close to O(nlogn) or even linear maybe using DP?

Title: Re: Longest Contiguous Subarray with average >=
Post by TenaliRaman on Dec 2^nd, 2011, 6:14pm

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

Title: Re: Longest Contiguous Subarray with average >=
Post by towr on Dec 3^rd, 2011, 11:15am

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

Title: Re: Longest Contiguous Subarray with average >=
Post by Grimbal on Dec 5^th, 2011, 4:43am

"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.

Title: Re: Longest Contiguous Subarray with average >=
Post by Grimbal on Dec 6^th, 2011, 2:48pm

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].

Title: Re: Longest Contiguous Subarray with average >=
Post by fizyka on Dec 6^th, 2011, 4:11pm

this is pretty difficult riddle, I think little simulation in C programming language will be highly recommended.
But how to build algorithm like this?

Title: Re: Longest Contiguous Subarray with average >=
Post by birbal on Dec 22^nd, 2011, 9:33am

on 12/06/11 at 14:48:44, Grimbal wrote:

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]

Title: Re: Longest Contiguous Subarray with average >=
Post by Dufus on Dec 25^th, 2011, 2:56am

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.