Description
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Examples
Input:
nums = [-2,1,-3,4,-1,2,1,-5,4]Output:
6Explanation:
The subarray [4,-1,2,1] has the largest sum = 6.
Input:
nums = [1]Output:
1Explanation:
With only one element, that element itself is the maximum subarray sum.
Input:
nums = [5,4,-1,7,8]Output:
23Explanation:
All elements are positive except one small negative (-1), so including all elements (5+4-1+7+8=23) yields the maximum sum.
Input:
nums = [-1]Output:
-1Explanation:
Single negative element - must include at least one number.
Constraints
- •
1 ≤ nums.length ≤ 10⁵ - •
-10⁴ ≤ nums[i] ≤ 10⁴