# Python O(n) solution and divide-and-conquer O(nlogn) solution

• O(n) solution:

``````class Solution:
# @param {integer[]} nums
# @return {integer}
def maxSubArray(self, nums):
if not nums:
return 0
dp = [0 for i in xrange(len(nums))]
dp[0] = nums[0]
for i in xrange(1, len(nums)):
dp[i] = max(nums[i], dp[i-1] + nums[i])
return max(dp)
``````

Idea:

1. Divide the array into two parts

2. Find maximum subarray sum for left half

3. Find maximum subarray sum for right half

4. Find maximum subarray sum for the subarray including the 2 middle elments

5. return the maximum of 2), 3) and 4)

class Solution:
# @param {integer[]} nums
# @return {integer}
def maxSubArray(self, nums):
if len(nums) == 0:
return 0
return self.maxSubArrayHelper(nums, 0, len(nums)-1)

`````` def maxSubArrayHelper(self, nums, low, high):
if low == high:
return nums[low]
mid = (low + high) / 2
leftSub = self.maxSubArrayHelper(nums, low, mid)
rightSub = self.maxSubArrayHelper(nums, mid+1, high)

leftMax, rightMax = nums[mid], nums[mid+1]
tmpSum = 0
for i in xrange(mid, low-1, -1):
tmpSum += nums[i]
leftMax = tmpSum if tmpSum > leftMax else leftMax
tmpSum = 0
for i in xrange(mid+1, high+1):
tmpSum += nums[i]
rightMax = tmpSum if tmpSum > rightMax else rightMax
return max(max(leftSub, rightSub), leftMax+rightMax)
``````

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