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

## Question

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

subarray is a contiguous part of 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 = [1]
Output: 1
```

Example 3:

```Input: nums = [5,4,-1,7,8]
Output: 23
```

Constraints:

• `1 <= nums.length <= 105`
• `-104 <= nums[i] <= 104`

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.

## Python Solution

```class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums)==1:
print(nums[0])

global_max = nums[0]
current_sum = nums[0]

for i in range(1,len(nums)):
current_sum = max(current_sum+nums[i],nums[i])
global_max = max(current_sum,global_max)

return global_max```