Maximum Subarray

# Maximum Subarray Given an integer array `nums`, find the **subarray** with the largest sum, and return its sum. A **subarray** is a contiguous non-empty sequence of elements within an array. ## Example 1 ``` Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. ``` ## Example 2 ``` Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The entire array has the largest sum = 23. ``` ## Constraints - `1 <= nums.length <= 10⁵` - `-10⁴ <= nums[i] <= 10⁴` **Follow up:** If you have figured out the O(n) solution, try coding another solution using the **divide and conquer** approach, which is an interesting problem variation.