# 53\_Maximum Subarray

\[Easy]\[Array, Dynamic Programming]

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.

## Solution 1: dynamic programing, bottom-up

**Idea**:

* If we have the solution for nums\[0, n-1], what's the solution when we add one extra integer nums\[n-1]? There are two possibilities for the max in nums\[0, n]:
  1. nums\[n-1] is not included: in this case the max in nums\[0, n] equals to the max in nums\[0, n-1].
  2. nums\[n-1] is included: in this case we need to know the max in nums\[0, n-1] that includes nums\[n-2], which we call curMaxSum. Then update curMaxSum with the max of two cases: 1) just have nums\[n-1] itself; 2) add nums\[n-1] to curMaxSum.
* Need to store two values when we iterate over the nums: 1) the max of sum for any subarray; 2) the max of sum for subarray includes the last element.

**Time Complexity**: $$O(n)$$

**Space Complexity**: $$O(1)$$

```python
def maxSubArray(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    curMaxSum, maxSum = -sys.maxint, -sys.maxint
    for num in nums:
        curMaxSum = max(curMaxSum+num, num)
        maxSum = max(maxSum, curMaxSum)
    return maxSum
```

## Solution 2: Divide and Conquer, Recursive

**Idea**:

1. divides the array into left and right halves and recursively solves for both of them to get the max sum for each half.
2. For the right half, compute the max sum if the first element is included.
3. For the left half, compute the max sum if the last element is included.
4. Merge: the result for the combination of the 2 sub arrays is the maximum of the following :\
   1\. solution for left sub array,\
   2\. solution for right sub array,\
   3\. max sum in the left subarray with the last element + max sum in the right array with the first element

**Time Complexity**: $$O(n\log{n})$$

**Space Complexity**: $$O(1)$$

```python
def maxSubArray(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    def helper(left, right):
        if left == right:
            return nums[left]

        # split into two parts
        mid = left + (right - left)//2
        l, r = helper(left, mid), helper(mid + 1, right)

        # max sum if include the first element in the right part
        # linear search
        l1, m1 = nums[mid + 1], nums[mid + 1]
        for i in range(mid + 2, right + 1):
            l1 += nums[i]
            if l1 > m1:
                m1 = l1

        # max sum if include the last element in the left part
        # linear search        
        l2, m2 = nums[mid], nums[mid]
        for i in range(mid - 1, left - 1, -1):
            l2 += nums[i]
            if l2 > m2:
                m2 = l2

        return max(l, r, m1 + m2)

    return helper(0, len(nums) - 1)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/dynamic-programming/53maximum-subarray.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.