Maximum Subarray (D&C) Simulation

Interactive visualization of recursive segmentation, suffix/prefix crossing scans, and combination decisions forming the maximum subarray value.

Mechanics

Recursive decomposition yields two independent maxima plus crossing built via a linear pass anchored at midpoint. Suffix and prefix partial sums track running best; combining leverages structural exclusivity (exactly one of left/right/cross contains the optimal subarray). Depth ~ log n for balanced splits thus O(log n) stack usage.

Pseudocode Reference

1function maxSubarray(arr):
2  if length(arr) == 1: return arr[0]
3  mid = length(arr)//2
4  leftBest = maxSubarray(arr[0:mid])
5  rightBest = maxSubarray(arr[mid:])
6  crossBest = bestCrossing(arr, mid)
7  return max(leftBest, rightBest, crossBest)