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


  • 1
    H

    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)
    

    Divide and Conquer: O(nlogn) (click here for reference)

    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)
      

Log in to reply
 

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