Is this a O(n) divide and conquer solution?


  • 0
    S

    I checked some divide and conquer solution on the discussion forum, and it seems that most people when they handle the case that max subarray will extend both left and right regions, they use the loop to extend from mid points to two sides (is this potentially O(nlgn) in worst case? correct me if I am wrong). In my solution, I maintain 4 things: 1) the sum of max subarray of whole region, 2) the sum of max subarray starting from the left end of current region, 3) the sum of max subarray ending at the right end of current region, and 4) the total sum of current region.

    The key point is to update the values 2) and 3). For the case of 2), there are only two possibilities: the new max subarray starting from the left will either cross the mid point or not. If it does not cross, the max subarray starting from the left should stay the same, otherwise, it should cover the whole left region and the max subarray starting from the left end of right sub region.

    I this way, we do not need to use loop during conquer stage and it should be O(n) complexity (correct me if I am wrong). PS: the actually run time seems not fast, so I am wondering if my analysis is correct, thanks!

    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            # divide and conquer solution
            nums_len = len(nums)
            if nums_len == 0:
                return 0
            return self.maxSubArrayHelper(nums, 0, nums_len-1)[0]
            
        def maxSubArrayHelper(self, nums, left, right):
            """
            :rtype: max subarray
                    max subarray that starts from the left
                    max subarray that ends at the right
                    sum of all left to right
            """
            if left == right:
                return nums[left], nums[left], nums[left], nums[left]
                
            mid = left + (right-left)/2
            left_res = self.maxSubArrayHelper(nums, left, mid)
            right_res = self.maxSubArrayHelper(nums, mid+1, right)
            
            max_sub = max(left_res[0], right_res[0], left_res[2]+right_res[1])
            max_sub_left = max(left_res[1], left_res[3]+right_res[1])
            max_sub_right = max(right_res[2], right_res[3]+left_res[2])
            
            return max_sub, max_sub_left, max_sub_right, left_res[3]+right_res[3]

Log in to reply
 

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