Maximum Subarray
Description: Given an integer array nums, find the contiguous subarray with the largest sum and return that sum. The subarray must contain at least one element.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Subarray [4,-1,2,1] has sum 6
Example 2:
Input: nums = [-3,-1,-5]
Output: -1
Explanation: All numbers are negative, take the largest
Constraints:
1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
Recommended time and space complexity
Aim for O(n) time and O(1) space.
Hint 1
Brute force over all subarrays is O(n²). Can you do a single pass?
Hint 2
Move left to right keeping the best sum ending at the current position.
Hint 3
At each step: extend the previous subarray or start fresh. Take the maximum.