> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/leetcode/53.-maximum-subarray.md).

# 53. Maximum Subarray

<https://leetcode.com/problems/maximum-subarray/description/>

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

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

**Solution1: (Dynamic Programming)**

$$\text{MaxSum}={A\[i],\ r\_{i-1}+A\[i]}$$&#x20;

```
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        CurrentSum = nums[0]
        MaxSum = nums[0]
        for i in range(1, len(nums), 1):
            if nums[i] + CurrentSum > nums[i]:
                CurrentSum = nums[i] + CurrentSum
            else:
                CurrentSum = nums[i]
            if CurrentSum > MaxSum:
                MaxSum = CurrentSum
        return MaxSum
```

**Solution2:**

```
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        self.nums = nums
        return self.findmax(0, len(nums)-1)
    
    def findmax(self, start, end):
        if start == end:
            return self.nums[start]
        mid = (start + end)/2
        maxleft = self.findmax(start, mid)
        maxright = self.findmax(mid+1, end)
        maxmid = self.nums[mid]
        current = self.nums[mid]
        for i in range(mid-1, start-1, -1):
            current += self.nums[i]
            if current > maxmid:
                maxmid = current
        current = maxmid
        for i in range(mid+1, end+1, 1):
            current += self.nums[i]
            if current > maxmid:
                maxmid = current
        return max(maxleft, maxmid, maxright)
```