EPI Python - find_maximum_subarray for array with negative numbers

#1

On page 245, the example code for finding the maximum contiguous subarray sum seems to return 0 when the array contains only negative numbers. Is this expected? I believe it would be better to return an actual value from the array.

It fails on this leetcode question: https://leetcode.com/problems/maximum-subarray

I solved it using an alternative solution (below) but I’m wondering if we could adapt the books’ solution to contemplate negative numbers?

Thanks!

class Solution(object):
def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    max_current = max_global = nums[0]
    for i in range(1,len(nums)):
        max_current = max(nums[i], nums[i] + max_current)
        if max_current > max_global:
            max_global = max_current

    return max_global
2 Likes
#2

I have a different version of the book so do not know the solution you are referring to. But the solutions on github as of writing seem incorrect. This will do the job.

def find_maximum_subarray(A):

    max_seen = -float('inf')
    max_end = 0
    for a in A:
        max_end = max(a, a + max_end)
        max_seen = max(max_seen, max_end)
    return max_seen
0 Likes