**Solution with discussion** https://discuss.leetcode.com/topic/80136/python-solution-with-detailed-explanation

**Maximum Subarray** https://leetcode.com/problems/maximum-subarray/

**Dynamic Programming **

```
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_so_far, curr_sum = -2**31, 0
for i in range(len(nums)):
if curr_sum+nums[i] < 0:
curr_sum, max_so_far = 0, max(max_so_far, nums[i])
else:
curr_sum, max_so_far = curr_sum + nums[i], max(max_so_far, curr_sum + nums[i])
return max_so_far
```

```
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_so_far, curr_sum = max(nums), 0
for i in range(len(nums)):
if curr_sum+nums[i] < 0:
curr_sum = 0
else:
curr_sum, max_so_far = curr_sum + nums[i], max(max_so_far, curr_sum + nums[i])
return max_so_far
```

**Divide and Conquer**

- Divide and Conquer solution, the solution can lie entirely in left or in right or span in between.
- When it spans in between, we can use principle of optimality. The middle sum can be broken into sum from middle-1 towards left, and sum from middle+1 towards an index <= high. Lets call these sums as lmax and rmax.
- Now the maximum middle sum must be max(lmax,0)+max(rmax,0)+nums[mid].
- Why? We have to include nums[mid]. Now the left sum or right sum will only be included if the sum is positive.

```
class Solution(object):
def maxSubArray(self, nums):
return self.helper(nums, 0, len(nums)-1)
def helper(self, nums, low, high):
if low > high:
return 0
if low == high:
return nums[low]
mid = low + (high-low)//2
x_left = self.helper(nums, low, mid)
x_right = self.helper(nums, mid+1, high)
lmax, rmax = float('-inf'), float('-inf')
lsum, rsum = 0,0
for i in range(mid-1, low-1, -1): ### Important Insight in NlgN solutions
lsum = lsum + nums[i]
lmax = max(lmax, lsum)
for i in range(mid+1, high+1, 1):
rsum = rsum + nums[i]
rmax = max(rmax, rsum)
return max(x_left, x_right, max(0,lmax)+max(0,rmax)+nums[mid])
```