359. How does the divide-and-conquer solution to maximum subarray work, and how does it compare with Kadane's algorithm?
MediumDivide & conquer
Technical
Show model answer
Split the array at the middle. The best subarray lies entirely in the left half, entirely in the right half, or crosses the middle. The crossing case is the best suffix of the left half plus the best prefix of the right half, computed in O(n). That gives T(n) = 2T(n/2) + O(n) = O(n log n) with O(log n) stack.
If each call returns four values (total sum, best prefix, best suffix, best overall), the combine step becomes O(1) and the recursion is O(n); this form also powers segment trees that answer range maximum-subarray queries. Kadane's algorithm is simpler for a single query: O(n) time, O(1) space.