53. Maximum Subarray

[tech-cow]

第一刷

练习DFS写法，没用DP
思路没问题，代码有BUG

错误代码

class Solution(object):
    def maxSubArray(self, nums):
        left, right = 0, len(nums) - 1
        return self.dfsHelper(self, nums, left, right)   # bug 1: self??????
    
    
    def dfsHelper(self, nums, left, right):
        # Base
        if left == right:
            return nums[left] #or right doesn't matter
        
        mid = (l + r) // 2    # bug 2: l + r???????? left + right....
         
        # Request
        leftSum = self.dfsHelper(nums, left, mid)
        rightSum = self.dfsHelper(nums, mid + 1, right)
        midSum = self.getMidSum(nums, left, mid , right)
        
        if leftSum >= rightSum and leftSum >= midSum:
            return leftSum
        
        if rightSum >= leftSum and rightSum >= midSum:
            return rightSum
        
        return midSum
        
        
        
    def getMidSum(self, nums, left, mid, right):
        leftSum, rightSum = -float('inf'), -float('inf')
        
        # Code
        tempSum = 0
        for i in range(mid + 1, left, -1):    # bug 3: should be the other way around
            tempSum += nums[i]  
            leftSum = max(leftSum, tempSum)
            
        tempSum = 0
        for j in range(mid + 1, right + 1):       
            tempSum += nums[j]
            rightSum = max(rightSum, tempSum)
        
        
        return leftSum + rightSum

正确代码

class Solution(object):
    def maxSubArray(self, nums):
        left, right = 0, len(nums) - 1
        return self.dfsHelper(nums, left, right)
    
    
    def dfsHelper(self, nums, left, right):
        # Base
        if left == right:
            return nums[left] #or right doesn't matter
        
        mid = (left + right) // 2
        
        # Request
        leftSum = self.dfsHelper(nums, left, mid)
        rightSum = self.dfsHelper(nums, mid + 1, right)
        midSum = self.getMidSum(nums, left, mid , right)
        
        if leftSum >= rightSum and leftSum >= midSum:
            return leftSum
        
        if rightSum >= leftSum and rightSum >= midSum:
            return rightSum
        
        return midSum
        
        
        
    def getMidSum(self, nums, left, mid, right):
        leftSum, rightSum = -float('inf'), -float('inf')
        
        # Code
        tempSum = 0
        for i in range(mid, left - 1, -1):
            tempSum += nums[i]
            leftSum = max(leftSum, tempSum)
            
        tempSum = 0
        for j in range(mid + 1, right + 1):
            tempSum += nums[j]
            rightSum = max(rightSum, tempSum)
        
        return leftSum + rightSum