Maximum Subarray
Given an integer array nums, find the contiguous non-empty subarray within nums that has the largest sum.
Return the maximum possible subarray sum.
A subarray is a contiguous part of an array. Your solution should run in O(n) time.
Example 1
Input
nums = [-2,1,-3,4,-1,2,1,-5,4]Output
6The subarray [4, -1, 2, 1] has the largest sum, which is 6.
Example 2
Input
nums = [1]Output
1The only subarray is [1], so the maximum sum is 1.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4