Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I try to solve this problem. The algorithm I developped has a complexity of $O(n^2)$. When dealing with large data the program is brought to its knees. Do you have any idea that might be faster than a quadratic algorithm? I summarize the problem briefly: Let A be a one dimensional array containing both positive and negative values, and also suppose a k. What we are searching is the size of the biggest subarray whose average is bigger than k or even equal. k is an integer and the array contains only integers.
For example if k=0 and A[] = -8 3 -1 -1 -1 -1 -1 2 -11. The output should be 7 (from A[2] to A[8].
Another simpler example 1 10 -1 -1 4 -1 7 2 8 1 . The output should be 3.

share|improve this question
1  
Reduce by subtracting k from every entry to the case k=0. Now read Jon Bentley's Programming Pearls series to find a linear algorithm for maximum contiguous subarray with largest sum. Even if I have the problem wrong, the reading will benefit you. Gerhard "Computer Science Can Be Fun" Paseman, 2012.11.14 –  Gerhard Paseman Nov 14 '12 at 22:36
    
I think you are wrong. What interests me here is having max size subarray. On the other hand the problem you describe is different and solved by kadane's algorithm in $O(n)$ –  paramar Nov 15 '12 at 3:11
    
You can easily get down to $O(n \log n)$ by first sorting the array, then checking the subarray [0..0], then [0..1], then [0..2], etc. –  user21816 Nov 15 '12 at 4:00
1  
---I think you are wrong. What interests me here is having max size subarray.--- Gerhard is actually right. There is no difference between what he referred to and what you want in the Platonic world (once you know how to do one thing, you know how to do the other as well). As to the particular realizations, the procedure I described in my answer gives exactly what you were asking for. –  fedja Nov 15 '12 at 13:27

3 Answers 3

up vote 5 down vote accepted

If you are not in the mood to go to the library right away, here is a simple description:

1) Subtract $\kappa$ from everything ($N$ operations).

2) Replace $a_k$ by the partial sums $S_k=\sum_{j=1}^k a_j$ ($N$ operations).

Now you are looking for the pair $0\le k\le m\le N$ such that $S_k\le S_m$ with the largest difference $m-k$. Note that $S_k$ is necessarily the minimum of $S_1,\dots,S_k$ and $S_m$ is necessarily the maximum of $S_m,S_{m+1},\dots,S_{N-1}$. Don't forget $S_0$ (the empty sum)!

3) Mark all such minima going from the left and all such maxima going from the right ($5N$ operations or so). You will have a decreasing sequence of positive starting positions and a decreasing sequence of positive ending positions.

4) Start with the leftmost starting position and go along the possible ending positions from the left to the right until you get the rightmost that still works. Record the difference. Go to the next starting position and see how far you can move the ending position to fit now. Compare the difference with the previous one and record it if it is larger.

5) Repeat until you reach the end.

Note that you go left to right all the time never coming back, so these steps are linear as well. Probably, you can optimize a bit but I'm too lazy to think of how.

6) Once you finish debugging the program and get some free time, follow Gerhard's advice :).

Editing with response to comments:

I'm not sure what you guys are doing that it doesn't work for you, but here how it runs on

2 2 -1000 -1000 2 2 -2 2 2 2 2 -2 -2 2 2 -1000 -1000 2 2 2

with average 2:

Step 1: remove 2:

0,0,-1002,-1002,0,0,-4,0,0,0,0,-4,-4,0,0,-1002,-1002,0,0,0

Step 1: partial summation left to right:

0,0,0,-1002,-2004,-2004,-2004,-2008,-2008,-2008,-2008,-2008,-2012,-2016,-3018,-4020,-4020,-4020,-4020.

Step 3:

Min positions (strict!) counting from the left:

0: 0, 3: -1002, 4: -2004, 7: -2008, 12: -2012, 13: -2016, 14: -3018, 15: -4020,

Max positions (strict) counting from the right:

2: 0, 3: -2002, 6: -2004, 11: -2008, 12: -2012, 13: -2016, 14: -3018, 18: -4020,

Steps 4,5. Put the marker B (beginning-1) and E (end) at the leftmost possible positions: B=0,E=2. Record the length 2 and the interval [1,2]

Try moving E to the right with this B. Impossible.

Change B to 3 (value -1002). Try to move E to the right. Impossible

B=4 (-2004) Now E can go to te right to 6 (-2004). Same length. No record.

B=7 (-2008) E goes (from the previous position, not from the beginning!) to 11 (-2008) Length 4>2, interval [8,11]. Record.

B=12 (-2012) E goes to 12. Length 0, no record.

B=13 (-2016), E goes to 13. Length 0, no record.

B=14 (-3018), E goes to 14. Length 0, no record.

B=15 (-4020), E goes to 18. Length 3<4, no record, reached the end, terminate, output [8,11].

share|improve this answer
1  
Thank you for your support fedja, here and in the comment above. It appears you appreciate Jon Bentley, which I am also glad to see. Permit me an American salutation, please. Gerhard "Wishing You A Happy Thanksgiving" Paseman, 2012.11.16 –  Gerhard Paseman Nov 16 '12 at 16:48

fedja, I can't verify right now if you are correct (i.e. optimal solution) but you are certainly not linear.

e.g. take avg temp = 2 and the following values

2 2 -1000 -1000 2 2 -2 -2 2 2 2 2 -2 -2 2 2 -1000 -1000 2 2 2

I can put $\frac{n}{2}$ blocks of (-1000 -1000) with small values between then and an avg temp near zero...

I don't think there is a linear time algo for this.

share|improve this answer

@fedja Can you explain a bit more your algorithm with an actualy example cause I cannot make it work . For example if you can demonstrate it for the example paramar gives. Ty!

share|improve this answer
1  
Done, though I used the example of Anonymous coward to convince him as well :). –  fedja Nov 21 '12 at 17:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.