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