Largest-sum run of consecutive elements

Given an array of positive and negative numbers, find the contiguous block of elements whose sum is as large as possible.

Kadane's algorithm: one pass, $O(n)$ time, $O(1)$ space. Track the best sum of a block ending at the current element, $b_i=\max(a_i,\,b_{i-1}+a_i)$, and the best value of $b_i$ seen so far, recording start and end indices when it improves. A negative running sum can never help later, so the block restarts there; if all entries are negative the answer is the largest single element.