# Leetcode: Maximum Subarray

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/maximum-subarray
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
## Basic Ideas: Dynamic programming
##              Get sums[i]: it's the sum from nums[0] to nums[i]
##
##              f(n) = max(f(n-1), sums[n], sums[n] - min(sums))
##
## Complexity: Time O(n), Space (n)
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
sums = [0] * length
sum_v = 0
for i in range(0, length):
sum_v += nums[i]
sums[i] = sum_v

# start from the very beginning
min_sum = 0
max_list = [0]*length
# the first element
max_list[0] = sums[0]
for i in range(0, length-1):
min_sum = min(min_sum, sums[i])
max_list[i+1] = max(max_list[i], sums[i+1], sums[i+1]-min_sum)
return max_list[-1]
```

<div style=”overflow: hidden;”>