pythonalgorithmdata-structureskadanes-algorithm

Debugging: Largest Sum Contiguous Subarray


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?


Solution

  • 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