leetcode-dp

53. Maximum Subarray.py

class Solution:   
    """
    Divide and Conquer:
    我們可以把我們要求的問題拆成不重複的子問題
        1.左邊subarray的最大連續合
        2.右邊subarray的最大連續合
        3.包含當前元素的的最大連續和
    用一個最小的例子[-2, 1]去展示你的idea
    [-2,1,-3,4,-1,2,1,-5,4]
      0 1. 2 3. 4 5. 6 7 8
      xxxxx.    i yyyy
      m = 0+(8-0)//2=4
      left_sum = 4 (maximum sum of contiguous left subarray)
      cross_sum = 3+3 (maximum sum of contiguous subarray including nums[m])
      right_sum = 4 (maximum sum of contiguous left subarray)
      
      return max(left_sum, cross_sum, right_sum)
      
      f([-2,1,-3,4,-1])
              i
      m = 0+(4-0)//2 = 2
      
      f([-2,1,-3])
      m = 0+(2-0)//2=1
      
      f([-2, 1])
      m = 0+(1-0)//2=0
      left_sum=-2
      right_sum=1
      cross_sum=1
      m = 0+(1-0)//2=0
      /      \
    f([2])   f([1])
    """
    def maxSubArray(self, nums: List[int]) -> int:
        def get_cross_sum(nums, left, right, mid):
            left_subsum = float("-inf")
            cross_sum = 0
            for i in range(mid, left-1, -1):
                cross_sum += nums[i]
                left_subsum = max(left_subsum, cross_sum)
            
            left_subsum = left_subsum if left_subsum != float("-inf") else 0
            right_subsum = float("-inf")
            cross_sum = 0
            for i in range(mid+1, right+1):
                cross_sum += nums[i]
                right_subsum = max(right_subsum, cross_sum)
            right_subsum = right_subsum if right_subsum != float("-inf") else 0
            #print("get_cross_sum", left, right, mid, left_subsum+right_subsum)
            return left_subsum+right_subsum
            
        def merge_sum(nums, left, right):
            if left == right:
                return nums[left]
            mid = left+(right-left) // 2
            left_sum = merge_sum(nums, left, mid)
            right_sum = merge_sum(nums, mid+1, right)
            cross_sum = get_cross_sum(nums, left, right, mid)
            return max(left_sum, right_sum, cross_sum)
            
        n = len(nums)
        return merge_sum(nums, 0, n-1)