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:
The array has only one element.
Input:
nums = [5,4,-1,7,8]Output:
23Explanation:
The entire array is the maximum subarray.
Input:
nums = [-1]Output:
-1Explanation:
Single negative element - must include at least one number.
Constraints
- •
1 ≤ nums.length ≤ 10⁵ - •
-10⁴ ≤ nums[i] ≤ 10⁴