I am trying to design an algorithm that computes the largest (by sum) contiguous subarray of an array of size n that uses a divide and conquer approach, but runs in linear time. The standard divide and conquer approach runs in O(nlogn) (can be found in chapter 4 of CLR) which is not what I am looking for. The following describes an O(n) divide and conquer algorithm: Page 16 https://software.intel.com/sites/default/files/m/d/4/1/d/8/10.1.1.150.7202.pdf however it goes over my head a little. Would anyone be able to shed some light on it?
2
-
1$\begingroup$ en.wikipedia.org/wiki/Maximum_subarray_problem, algorithmist.com/index.php/Kadane%27s_Algorithm, cs.stackexchange.com/q/43852/755, stackoverflow.com/q/7943903/781723. $\endgroup$D.W.– D.W. ♦2017-01-21 04:46:36 +00:00Commented Jan 21, 2017 at 4:46
-
1$\begingroup$ What is it that you don't understand. "I've read one explanation and I don't understand it; please give me another one!" isn't a good question, because the likely outcome is that somebody spends their time writing your another description of what the algorithm does, and you say "Sorry, don't understand that, either." $\endgroup$David Richerby– David Richerby2017-01-21 14:02:30 +00:00Commented Jan 21, 2017 at 14:02
Add a comment
|