Maximum Subarray Sum

Keep the best suffix

Let current be the maximum sum of any nonempty subarray ending at the current index. At value x, either start fresh at x or extend the previous suffix, so current = max(x, current + x). Maintain best = max(best, current). This is Kadane's algorithm, but state the invariant aloud: before advancing, current describes the best subarray forced to end here and best describes the best one seen anywhere.

Edge cases

Initialize both variables to the first element, rather than zero, so [-5,-2] returns -2. If the interviewer wants indices, record the tentative start whenever restarting and snapshot it when best improves. An empty-array convention should be clarified because common versions require a nonempty answer. The scan is O(n) time and O(1) auxiliary space. A divide-and-conquer solution is valid but slower at O(n log n) and is useful only if discussing segment-tree composition.