divide and conquer solution


  • 0
    D

    '''
    class Solution(object):
    def maxSubArray(self, nums):
    length = len(nums)
    mid = length // 2
    if length == 0:
    return None
    if length == 1:
    return nums[0]
    left = self.maxSubArray(nums[0:mid])
    right = self.maxSubArray(nums[mid:length])
    max_left = nums[mid-1]
    sum = 0
    for i in nums[0:mid][::-1]:
    sum += i
    if sum > max_left:
    max_left = sum

        max_right = nums[mid]
        sum = 0
        for i in nums[mid:length]:
            sum += i
            if sum > max_right:
                max_right = sum
        return max(left, right, max_left + max_right)
    

    '''


Log in to reply
 

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