# LeetCode 53. Maximum Subarray

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

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

Example 3:

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

Constraints:

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

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)

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

1. Vicky says:

/* Java solution */
class Solution {
public int maxSubArray(int[] nums) {
int max_so_far = nums;
int max_ending_here = nums;

for (int i=1;i<nums.length;i++) {
max_ending_here = Math.max(nums[i] + max_ending_here, nums[i]);
max_so_far = Math.max(max_ending_here, max_so_far);
}

return max_so_far;
}
}