Maximum Subarray

Problem

Find the contiguous subarray with the largest sum and return that sum. The subarray must contain at least one element.

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]  → 6    ([4, -1, 2, 1])
Input: [1]                                → 1
Input: [-1, -2, -3]                       → -1   (least-negative element)

Solution

Approach - Kadane's algorithm, a single-pass running maximum.

current_sum holds the largest sum of any subarray that ends at the current position. At each new element num you face exactly two choices: extend the subarray ending at the previous element (current_sum + num), or throw it away and start a fresh subarray at num alone. Taking max(num, current_sum + num) picks the better of the two. The crucial observation is that extending is worthwhile only when the previous current_sum is positive - if it is negative, it can only drag down whatever comes after, so restarting at num is strictly better. A separate max_sum records the best current_sum ever seen, because the optimal subarray can end anywhere, not just at the last index.

This works in one pass with no backtracking because the decision at each position is locally optimal and independent of the future: a negative running prefix never helps any later extension. Trace [-2, 1, -3, 4, -1, 2, 1, -5, 4]: the running sum collapses to 1 at the 1, restarts at 4, then climbs 4, 3, 5, 6 across -1, 2, 1 before -5 knocks it down. max_sum peaks at 6, the answer.

Edge cases - initializing both variables to nums[0] (not 0) is what makes an all-negative array like [-1, -2, -3] return the least-negative element -1 rather than a phantom empty subarray of 0. The subarray must hold at least one element, and this initialization guarantees it.

Complexity - O(n) time, O(1) space - one pass holding two scalars.