Checkpoint: Max Subarray, Defended

**Task.** Given n integers (possibly all negative), find the maximum sum of a non-empty contiguous subarray. **Constraints:** 1 ≤ n ≤ 200000; |a[i]| ≤ 10^9. **Process requirements (this is the mastery point):** - Verify on the all-negative case BEFORE trusting Kadane's dp[0] = 0 habit. - The answer for n = 3 equal 10^9 values is 3·10^9 — outside int range. - A single O(n) pass suffices; anything slower is wasted effort.