Maximum Subarray Theory

1. Linear Recurrence

current = max(a[i], current + a[i])
best = max(best, current)

2. All-Negative Arrays

Initialize current and best with first element to handle all negatives gracefully.

3. Variants

• Circular array: max(kadane(arr), total - minSubarray).
• Max product: maintain max and min product states.
• 2D max sub-rectangle: apply 1D Kadane over compressed column sums.