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
1 Like