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

Example:

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

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)

## 3 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;
}
}