Python solution with detailed explanation


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/80136/python-solution-with-detailed-explanation

    Maximum Subarray https://leetcode.com/problems/maximum-subarray/

    **Dynamic Programming **

    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            max_so_far, curr_sum = -2**31, 0
            for i in range(len(nums)):
                if curr_sum+nums[i] < 0:
                    curr_sum, max_so_far = 0, max(max_so_far, nums[i])
                else:
                    curr_sum, max_so_far = curr_sum + nums[i], max(max_so_far, curr_sum + nums[i])
            return max_so_far
    
    
    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            max_so_far, curr_sum = max(nums), 0
            for i in range(len(nums)):
                if curr_sum+nums[i] < 0:
                    curr_sum = 0
                else:
                    curr_sum, max_so_far = curr_sum + nums[i], max(max_so_far, curr_sum + nums[i])
            return max_so_far
    

    Divide and Conquer

    • Divide and Conquer solution, the solution can lie entirely in left or in right or span in between.
    • When it spans in between, we can use principle of optimality. The middle sum can be broken into sum from middle-1 towards left, and sum from middle+1 towards an index <= high. Lets call these sums as lmax and rmax.
    • Now the maximum middle sum must be max(lmax,0)+max(rmax,0)+nums[mid].
    • Why? We have to include nums[mid]. Now the left sum or right sum will only be included if the sum is positive.
    class Solution(object):
        def maxSubArray(self, nums):
            return self.helper(nums, 0, len(nums)-1)
        
        def helper(self, nums, low, high):
            if low > high:
                return 0
            if low == high:
                return nums[low]
            mid = low + (high-low)//2
            x_left = self.helper(nums, low, mid)
            x_right = self.helper(nums, mid+1, high)
            lmax, rmax = float('-inf'), float('-inf')
            lsum, rsum = 0,0
            for i in range(mid-1, low-1, -1): ### Important Insight in NlgN solutions
                lsum = lsum + nums[i]
                lmax = max(lmax, lsum)
            for i in range(mid+1, high+1, 1):
                rsum = rsum + nums[i]
                rmax = max(rmax, rsum)
            return max(x_left, x_right, max(0,lmax)+max(0,rmax)+nums[mid])        
    

Log in to reply
 

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