Maximum Subarray Sum

Problem: Given an array of integers (which may include negative numbers), find the contiguous subarray with the largest sum and return that sum.

Constraints: Array can contain negative numbers; must handle at least one element.

Example: Input: [-2,1,-3,4,-1,2,1,-5,4] -> Output: 6 (subarray [4,-1,2,1]).

Approach: Kadane's algorithm -- maintain a running "best sum ending here" as max(current element, running sum + current element), and track the global maximum seen so far. O(n) time, O(1) space.