Maximum Subarray

Kadane's algorithm keeps current, the maximum sum of a subarray ending exactly at the current index, and best, the maximum seen anywhere. For value x, either extend the previous ending subarray or start fresh: current = max(x, current + x), then update best. The invariant is that no subarray ending here can be better than those two possibilities, because every such subarray either began here or has a best predecessor ending one position earlier. Initialize both values from the first element, not zero, so an all-negative array returns its largest element rather than an empty subarray unless the contract explicitly permits empty. To reconstruct indices, reset a candidate start when x exceeds current+x and save the range when best improves. Test one value, all negative, all positive, zeros, and large sums requiring a wide numeric type. The method is O(n) time and O(1) extra space.