Medium
Find the contiguous subarray with the largest sum.
Given an integer array that may include negative values, return the maximum possible sum of any non-empty contiguous subarray.
Examples
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The best subarray is [4,-1,2,1].
Constraints
- 1 <= nums.length