DivideConquer Reci4

¶开始 Starting

经典题目，最大自序和 ，Recitation 4

¶题目 Question

The Maximum Subarray Problem: Suppose you are given an array of n integers. The integers may contain negative numbers. We want to find a (contiguous) subarray whose numbers sum to the most possible. For example, if A= (−5,−6,3,−2,7,−6,2,1), then the maximum subarray would be(3,−2,7)because it sums to 8 and there is no other subarray that sums that high. Solve the problem using divide and conquer, in time O(nlogn).

¶想法 Thinking

Brutal force will consider all possible subarrays, there are $n^2$ subarrays, so the total time is $O(n^2)$ time.

There are three possible ways of locating the ideal (i,j) for the max array:

1. in left half
2. in right half
3. in the region that cross the middle

The third case is not a recursion process. All three cases return the max array for that part.(Correctness).

The termination should be when high == low, return (low, high, A[low ])

After returning three cases, we should do comparison between them.

The recursion should return (lower, higher, sum)

和Reci 一样的解法：中文

最优解也并非这个 分治法，但是思维比较巧妙

https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-shi-yue-40/

¶算法 Algorithm

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        def crossMaxSubArray(nums, left, right, middle):
            # left part, summing
            leftSum = nums[middle]
            return_i = middle
            i = middle -1
            while i >= left:
                currentSum = sum(nums[i:middle+1])  # middle is included in this case
                if currentSum >leftSum:
                    leftSum = currentSum
                    return_i = i
                i-=1
            
            # right part
            rightSum = nums[middle+1]
            return_j = middle + 1
            j = middle +1
            while j <= right:
                currentSum = sum(nums[middle+1:j+1]) # j is not included in this case 
                if currentSum > rightSum:
                    rightSum = currentSum
                    return_j = j
                j+=1
            
            
            totalSum = leftSum+rightSum
            return (return_i, return_j, totalSum)
        
        def recursionMax(nums, left, right):
            # base case
            if (left == right):
                return (left, right, nums[left])
            
            middle = (right+left)//2
            (leftLow, leftHigh, leftSum) = recursionMax(nums, left, middle)
            (rightLow, rightHigh, rightSum) = recursionMax(nums, middle+1, right)
            (crossLow, crossHigh, crossSum) = crossMaxSubArray(nums, left, right, middle)
            # comparison
            if leftSum >= rightSum and leftSum >= crossSum:
                return (leftLow, leftHigh, leftSum)
            elif rightSum >= leftSum and rightSum >= crossSum:
                return (rightLow, rightHigh, rightSum)
            elif crossSum >= leftSum and crossSum >= rightSum:
                return (crossLow, crossHigh, crossSum)
            
        (_,_, s) = recursionMax(nums, 0, len(nums)-1)
        
        return s

¶运行时间 Run-time

T(n) = 2T(n/2) + O(1) (comparing) + O(n)(cross) + O(1)(sum)

​ = 2T(n/2) + O(n)

​ = O(nlogn) by mastering theorem

¶反思 Introspection

因为在cross 里面的boundary 里面的bug改来改去，就是做不好，仔细看了好一会（1个小时以上）才发现是一个小错误。所以一定要在脑子里想好boundary 的情况！！！

おやすみ