## Description

https://leetcode.com/problems/maximum-subarray/

Given an integer array `nums`

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

**Example:**

Input:[-2,1,-3,4,-1,2,1,-5,4],Output:6Explanation:[4,-1,2,1] has the largest sum = 6.

**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.

## Explanation

The contiguous subarray which has the largest sum starts from the contiguous subarray which has the smallest sum.

## Python Solution

```
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0
prefix_sum = 0
max_sum = -sys.maxsize
min_sum = sys.maxsize
for num in nums:
prefix_sum += num
max_sum = max(max_sum, prefix_sum, prefix_sum - min_sum)
min_sum = min(min_sum, prefix_sum)
return max_sum
```

- Time complexity: O(N)
- Space complexity: O(1)

## 2 Thoughts to “LeetCode 53. Maximum Subarray”