Maximum Subarray Sum — Solution & Editorial

Back to the Problem

Kadane's algorithm: the best subarray ending at i either extends the previous best or restarts at a_i. Track the global maximum.

Complexity: O(N)

Watch out: All-negative inputs: the answer is the largest single element, so never clamp the running sum at 0.