Problem
Given an integer array, find the contiguous subarray with the largest sum and return that sum. The subarray must contain at least one element.
Input / Output
- Input: int array nums (may contain negatives).
- Output: the maximum contiguous subarray sum.
Constraints
- 1 ≤ n ≤ 10^5; values may be negative, so the answer can be negative (an all-negative array).
- O(n) time expected.
Example
- [-2,1,-3,4,-1,2,1,-5,4] → 6 (subarray [4,-1,2,1]).
- [-3,-1,-2] → -1 (best is the single largest element).