LC53 Maximum subarray

Brute force

Try out all O(n^2) subarray and return the max sum.

Dynamic programming

The basic idea is to record all the maximum subarray that ends at all i. and return the max.

How to construct a maximum subarray

If we have had a maximum subarray that ends on i – 1, to determine the maximum subarray that ends on i, we can either

  1. add maximum subarray that ends on i – 1 with nums[i]
  2. start a new maximum subarray with only nums[i]

We will choose 1 if max_subarray[i – 1] + nums[i] > nums[i].

Base case:

At the beginning, max_subarray[0] = nums[0]

        if not nums:
            return -1
        max_sub = [0] * len(nums)
        max_sub[0] = nums[0]
        for i in range(1,len(nums)):
            max_sub[i] = max(max_sub[i - 1] + nums[i], nums[i])

        return max(max_sub)

Divide and conquer

def maxSubArray(self, nums: 'List[int]') -> 'int':
        """

        """
        def find_mid(nums, l, r, m):
            """
            Find the maxsubarray that ends on m,
            and the maxsubarray that starts on m + 1, concat th eresult
            """
            cur_sum = 0
            left_sum = - float('inf')
            for i in range(m, l - 1, -1):
                cur_sum += nums[i]
                left_sum = max(left_sum, cur_sum)
            right_sum = - float('inf')
            cur_sum = 0
            for i in range(m + 1, r + 1):
                cur_sum += nums[i]
                right_sum = max(right_sum, cur_sum)

            return right_sum + left_sum



        def find_recur(nums, l, r):
            if (l == r):
                return nums[l]

            m = (l + r) // 2

            return max(find_recur(nums, l, m),
                       find_recur(nums, m + 1, r),
                       find_mid(nums, l, r, m))

        return find_recur(nums, 0, len(nums) - 1)

Bugs

Didn’t init the left_sum and right_sum to -float(‘inf’).

In case of nums of size 2. The find middle will simply return 0. But the middle didn’t include anything so we should return -inf in that case.

Find middle

At first, I did something more complicated so my code can strictly divide the three cases:
EG in [1,2,3,4] left would be [1] right would be [4] and middle would be [2,3]. But it leads to complicated code because you have to divide cases into even and odd and so on.

a simpler solution

We can just use (l + r) //2 as the middle and find the max subarray that contains the middle.
It might overlap.
[10,20,-1,-1] we have l = 0, m = 1 and r = 3. find_recur(nums, l, m) will find the max subarray in [10, 20]. It is 30. find_mid will find the maxsubarray that contains nums[m]. In this case, find_mid finds 30 as well. But overlap is ok because we only want the max.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax