Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

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 = 
Output: 1

Example 3:

Input: nums = 
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-2147483647]
Output: -2147483647

Constraints:
-1 <= num.length <= 2*10^4

-2^{31} <= num[i] <= 2^{31}-1

Solution in python:

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
sum_value = 0
max_subseq = nums
for i in range(len(nums)):
sum_value += nums[i]
if sum_value > max_subseq:
max_subseq = sum_value
if sum_value < 0:
sum_value = 0;
return max_subseq

Complexity analysis:

• Time complexity:O(n).
• Space complexity:O(1).

2.Divide and conquer

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def max_subseq(left, right, num):
if left == right:
return num[left]
middle = (left+right)//2
max_left = max_subseq(left, middle, num)
max_right = max_subseq(middle+1, right, num)
sum_left = sum_right = 0
i, j= middle, middle + 1
max_middle_left = num[i]
max_middle_right = num[j]
while i >= left:
sum_left += num[i]
if sum_left >= max_middle_left:
max_middle_left = sum_left
i -= 1
while j <= right:
sum_right += num[j]
if sum_right >= max_middle_right:
max_middle_right = sum_right
j += 1
max_middle = max_middle_left + max_middle_right
return max(max_left, max_middle, max_right)
return max_subseq(0, len(nums)-1, nums)

Complexity analysis:

• Time complexity:O(n\log_{}n).
• Space complexity:O(\log_{}n).