Debugging: Largest Sum Contiguous Subarray

Question

I'm solving a question that asks for the Largest Sum Contiguous Subarray. I know that this problem can be solved by using Kadane's Algorithm but I don't know the algorithm so I tried to code the problem on my own.

Here's the code I wrote:

def maxSubarray(arr): # 'arr' is the list for which we have to calculate the maximum sum
    h1 = arr[0]
    h2 = arr[1]
    subset_sum = -sys.maxsize-1
    for i in range(1,len(arr)):
        h1 = max(h2,h1+arr[i])
        subset_sum = max(h1,subset_sum)
    subset_sum = max(max(arr),subset_sum) # This is used if all elements in the list are negative

But this code's not giving the correct output and I can't seem to figure out what's going wrong? Can anyone help me out?

Answer 1

You are not updating h2 with each iteration.

Rather than updating, you can directly use arr[i] in finding the maximum.

def maxSubArray(self, arr: List[int]) -> int:
        h1 = arr[0]
        subset_sum = -sys.maxsize-1
        for i in range(1,len(arr)):
            h1 = max(arr[i],h1+arr[i])
            subset_sum = max(h1,subset_sum)
        subset_sum = max(max(arr),subset_sum)
        return subset_sum