Maximum Subarray - D&C

Problem: Find contiguous subarray with maximum sum.

D&C: Split in half. Max subarray is in left half, right half, or crossing middle.

Crossing: Extend left from mid, extend right from mid+1, sum both max extensions.

function maxCrossing(arr, left, mid, right):
    leftMax = extend left from mid
    rightMax = extend right from mid+1
    return leftMax + rightMax

Time: $O(n \log n)$. Kadane's is $O(n)$, but D&C illustrates the technique.