Python solution with detailed explanation

• 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])
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.