Maximum Subarray

Initialize ending and best to the first value. For each later value x, set ending = max(x, ending + x): an optimal subarray ending here either starts here or extends the optimal subarray ending one position earlier. Then update best = max(best, ending). This examines the best candidate for every possible final index, so it covers every non-empty contiguous subarray. Initialization from the first value is important because an all-negative array must return its largest element, not zero. The algorithm runs in O(n) time and uses O(1) extra space. If the actual subarray is required, track a tentative start when the algorithm chooses x, and save the start and current end whenever best improves. Divide-and-conquer is possible in O(n log n) but is unnecessary here.