Timeline for Largest subarray with average $\geq$ k
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 1, 2015 at 2:50 | answer | added | SHAN | timeline score: 1 | |
| Nov 21, 2012 at 12:52 | vote | accept | paramar | ||
| Nov 21, 2012 at 12:51 | vote | accept | paramar | ||
| Nov 21, 2012 at 12:52 | |||||
| Nov 15, 2012 at 13:27 | comment | added | fedja | ---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. | |
| Nov 15, 2012 at 4:00 | comment | added | user21816 | 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. | |
| Nov 15, 2012 at 3:11 | comment | added | paramar | 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)$ | |
| Nov 14, 2012 at 23:16 | answer | added | fedja | timeline score: 8 | |
| Nov 14, 2012 at 22:36 | comment | added | Gerhard Paseman | 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 | |
| Nov 14, 2012 at 22:20 | history | edited | paramar | CC BY-SA 3.0 |
edited title
|
| Nov 14, 2012 at 22:02 | history | asked | paramar | CC BY-SA 3.0 |