~O(n) SubArray Divide and Conquer Solution


  • 0
    B
    class Solution:
    
    def maxSubHelper(self, A, left, right):
        if(right == left): return A[left]
        
        middle = (left+right)/2
        
        leftans = self.maxSubHelper(A, left, middle)
        rightans = self.maxSubHelper(A, middle+1, right)
        
        leftmax = A[middle]
        rightmax = A[middle+1]
        
        temp = 0
        for i in range(middle, left-1, -1):
            temp += A[i]
            leftmax = max(leftmax, temp)
    
        temp = 0
        for i in range(middle+1, right+1):
            temp += A[i]
            rightmax = max(rightmax, temp)
    
        return max(max(leftans, rightans),leftmax+rightmax)
    
    # @param {integer[]} nums
    # @return {integer}
    def maxSubArray(self, nums):
        if not len(nums): return 0
        return self.maxSubHelper(nums, 0, len(nums)-1)

Log in to reply
 

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