 # 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
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

#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