maximum subarray

class (object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        cur_sum = 0
        cur_min = 0
        total_max = -sys.maxint
        for i in range(len(nums)):
            cur_sum += nums[i]
            total_max = max(total_max, cur_sum - cur_min)
            cur_min = min(cur_min, cur_sum)
        
        return total_max

class (object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return -sys.maxint
        if len(nums) == 1:
            return nums[0]
        # 来试试divide and conquer
        mid = len(nums) / 2
        # 如果max array 不包含mid
        left_max = self.maxSubArray(nums[:mid])
        right_max = self.maxSubArray(nums[mid+1:])
        # 如果max array 包含mid
        # max  = nums[mid] + right side max prefix sum, + left side max postfix sum
        mid_max = self.maxMid(nums, mid)
        
        return max(left_max, right_max, mid_max)
    
    def maxMid(self, nums, mid):
        prefix_sum = [0]
        for i in range(mid+1, len(nums)):
            prefix_sum.append(nums[i]+prefix_sum[-1])
        
        postfix_sum = [0]
        for i in range(mid - 1, -1, -1):
            postfix_sum = [nums[i]+postfix_sum[0]] + postfix_sum
        if mid == len(nums) - 1:
            return nums[mid] + max(postfix_sum)
        elif mid == 0:
            return nums[mid] + max(prefix_sum)
        else:
            return nums[mid] + max(prefix_sum) + max(postfix_sum)