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.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ 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 $\endgroup$– Gerhard PasemanCommented Nov 14, 2012 at 22:36
-
$\begingroup$ 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)$ $\endgroup$– paramarCommented Nov 15, 2012 at 3:11
-
$\begingroup$ 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. $\endgroup$– user21816Commented Nov 15, 2012 at 4:00
-
1$\begingroup$ ---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. $\endgroup$– fedjaCommented Nov 15, 2012 at 13:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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].
-
1$\begingroup$ 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 $\endgroup$ Commented Nov 16, 2012 at 16:48
$\begingroup$
$\endgroup$
This can be solved in O(n) time and O(n) space complexity:
I have added a post here: https://stackoverflow.com/questions/13476927/longest-contiguous-subarray-with-average-greater-than-or-equal-to-k/32322738#32322738
Code can be found at: http://codeshare.io/Y1Xc8
Let me know your thoughts.
