Revision as of 21:26, 7 January 2018 edit SineBot (talk \| contribs) Bots 2,564,948 edits m Signing comment by Poitevinpm - "" ← Previous edit		Revision as of 21:47, 7 January 2018 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,862 edits →Erroneous (or confusing) divide and conquer version: 2c Next edit →
Line 84: The divide and conquer version of the maximum subarray is notoriously O(n lg n) (see CLRM for instance as a reference.) I have trouble understanding the solution, for instance, what sum[f - 1] and sum[f]? the only array defined clearly in the problem is a, I don't know what sum is supposed to contain. An additional explanation would be great. <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Poitevinpm\|Poitevinpm]] ([[User talk:Poitevinpm#top\|talk]] • [[Special:Contributions/Poitevinpm\|contribs]]) 21:25, 7 January 2018 (UTC)</small> <!--Autosigned by SineBot--> :For my own part, I don't understand why other editors insist on devoting so much of the space in the article (and in textbooks like CLRS) to bad algorithms like the brute force and divide and conquer ones, when Kadane's algorithm is so simple (simpler than the divide and conquer) and in all respects better. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 21:47, 7 January 2018 (UTC)

Talk:Maximum subarray problem: Difference between revisions